多項式時間（卡普）歸約（polynomial-time reduction）
/ Karp = karp /
假設你已經會解問題 B，而你面對一個新問題 A。歸約是一種解 A 的辦法：悄悄把 A 的每個實例翻譯成 B 的一個實例，問你的 B 求解器，再原封不動地回報它的答案。若翻譯夠快，那麼「A 不比 B 難」——任何解 B 的好演算法都免費給了你一個解 A 的。這就和「我會算三角形面積，所以要算任意多邊形的面積，我把它切成三角形」是同一招：重用一個已解問題去攻破未解的。
精確地說，從決定問題 A 到決定問題 B 的多項式時間（卡普）歸約，是一個可在多項式時間內計算的函數 f，把 A 的每個實例 x 映到 B 的一個實例 f(x)，使得「x 是 A 的『是』實例，當且僅當 f(x) 是 B 的『是』實例」。我們記作 A <=p B。兩個要求是：f 在多項式時間內執行，且它精確地「保持」答案（是映到是、否映到否）。注意 f 只「呼叫 B 求解器一次」，並直接回傳其判決——這就是「多對一」的意思，有別於可多次呼叫 B 的較寬鬆的圖靈歸約。多項式預算的用意在於它本身不能偷渡困難工作：若 B 屬於 P 且 A <=p B，則 A 也屬於 P，因為「先翻譯再求解」是多項式加多項式。
歸約是整門學科的承重工具，原因在於它「保持」並「轉移」了什麼。「屬於 P」往前流（B 容易蘊含 A 容易）；「困難」往後流（A 困難蘊含 B 困難）。而 <=p 具有遞移性——若 A <=p B 且 B <=p C 則 A <=p C——這讓單一個困難問題（SAT）能透過一連串歸約，孕育出一整座困難問題的動物園。關於「方向」有個誠實的提醒，這也是最常見的錯誤：「A 歸約到 B」意指 B 至少和 A 一樣難，而「不是」說 A 困難或 B 容易。要證明一個新問題 X 是 NP 困難，你要把一個「已知困難」的問題歸約「到」X（已知 <=p X），絕不能反過來。
把獨立集歸約到團。給定 (G, k)，建出補圖 G'（相同頂點；G' 中有邊恰好在 G 沒有邊之處）。那麼「G 有大小為 k 的獨立集」當且僅當「G' 有大小為 k 的團」，因為非邊變成了邊。建出 G' 是 O(n^2)——多項式——且答案被保持，所以 independent-set <=p clique。
f 在多項式時間內、保持答案地映射實例：是對是、否對否，B 只被求解一次。
注意方向。A <=p B 意指 B 至少和 A 一樣難。要證明 X 是 NP 困難，要把一個已知困難的問題歸約「進」X，而非把 X 歸約到別處。而且這個映射必須在「當且僅當」的「兩個方向」上都保持答案——單向蘊含不是合法的卡普歸約。