歸約（reduction）

想像你只有一台會做乘法的計算機，有人交給你一個求平方的任務：算出 n 的平方。你不需要新工具，只要把新任務翻譯成舊任務：把 n 和 n 餵進乘法器，讀出答案即可。歸約正是這種翻譯。它把你想解的問題，轉換成你已經會解的問題，並保證對後者的答案能直接給出前者的答案。

更精確地說，從問題 A 到問題 B 的歸約，是一套做法：給定 A 的任何實例（輸入），就產生一個 B 的實例，並保證 B 的答案能告訴你 A 的答案。如果你又握有一個能解 B 的方法，現在就能解 A：把 A 的實例翻譯成 B 的實例，解 B，再把答案翻回來。我們說 A 歸約到 B，常寫作 A <= B，讀作「A 不比 B 難」。依賴的箭頭只朝一個方向：能解 B 就能解 A，所以 B 至少和 A 一樣難。在計算理論裡，我們堅持翻譯本身必須是可計算的（圖靈機能執行它），這樣歸約才不會偷偷夾帶任何不可計算的能力。

歸約是整個學科的主力工具，用在兩個感覺相反的方向。要證明某問題可解，就把它歸約到你已會解的問題。要證明某問題很難或不可能，就把一個已知很難的問題歸約到它身上：若 A 不可判定且 A <= B，則 B 也必定不可判定，因為一個 B 的解法會給出一個 A 的解法。把這個方向搞反，是學生最常犯的單一錯誤，務必小心（見「歸約方向」）。同樣的想法之後會再度出現——這次計算的是資源而非單純的可解性——成為定義 NP 完全的多項式時間歸約。