多項式時間歸約（polynomial-time reduction）
/ Karp -> KARP /
歸約是把一個問題翻譯成另一個的翻譯員，你已在「轉移不可判定性」那裡見過它。多項式時間歸約是同一個想法、外加一只碼錶：翻譯本身必須跑得快，在多項式時間內完成。它讓你能在計較資源的 P 與 NP 世界裡說「問題 A 不比問題 B 難」——在那裡，速度（而非單純的可解性）才是貨幣。
精確地說，從問題 A 到問題 B 的多項式時間多一歸約（寫作 A <=p B），是一個可在多項式時間內計算的函數 f，使得對每個輸入 x：x 是 A 的是實例，當且僅當 f(x) 是 B 的是實例。要在輸入 x 上判定 A，你就計算 f(x) 再去問 B。這個「當且僅當」讓是映到是、否映到否，不翻轉。因為 f 在多項式時間內執行，輸出 f(x) 也只有多項式大小，這很重要：若 B 後來證明可在多項式時間內求解，則「先算 f、再解 B」這個組合仍是多項式，所以 A 也可在多項式時間內求解。
這個組合性質正是整套 NP 完全理論的引擎。若 A <=p B 且 B 屬於 P，則 A 屬於 P。讀其逆否命題，它就成了難度工具：若 A 很難且 A <=p B，則 B 很難。多項式時間歸約也具遞移性（A <=p B 且 B <=p C 給出 A <=p C），這恰恰讓單一個難題能透過一連串歸約把難度散布到成千上萬個其他問題上。方向是一切：要證明 B 是 NP 困難，你把一個「已知很難」的 A 歸約到 B，絕不反過來。
獨立集在多項式時間內歸約到團問題：給定一張圖 G 與數 k，在平方時間內建出補圖 G-bar（把每條邊翻成非邊、反之亦然）。則 G 有大小為 k 的獨立集，當且僅當 G-bar 有大小為 k 的團。翻譯 f(G, k) = (G-bar, k) 就是整個歸約。
A <=p B：一個多項式時間函數把是實例映成是實例，於是 B 的解法只多付出多項式開銷就成了 A 的解法。
方向是經典陷阱：A <=p B 意指 B 至少和 A 一樣難，不是反過來。要證明目標很難，就把一個已知很難的問題歸約「到」你的目標。