映射歸約（mapping reduction）
映射歸約是最整潔、限制最嚴的一種歸約：用單一個可計算函數，把每個「是」實例改寫成「是」實例、每個「否」實例改寫成「否」實例。可以想成一位萬無一失的翻譯員，把每個英文的是非題忠實地譯成法文是非題，忠實到法文的答案永遠與英文一模一樣。你完全不必思考；只要翻譯問題、問一次，答案原封不動地回來。
形式上，語言 A 映射歸約到語言 B，寫作 A <=m B，是指存在一個可計算（全函數、總會停機）的函數 f，使得對每個字串 w，w 屬於 A 若且唯若 f(w) 屬於 B。這個「若且唯若」是核心：是映到是、否映到否，不翻轉、無例外。「多一」這名稱記錄了 f 可以把許多不同字串送到同一個目標，卻絕不會把一個字串拆成需要兩個答案的問題。關鍵是 f 在概念上只呼叫 B 一次，並逐字採用其答案——這恰好是圖靈歸約的另一個極端，後者可多次向 B 的神諭發問並重塑答案。
映射歸約是轉移可判定性與可識別性的精確工具。若 A <=m B，則：B 可判定則 A 也可判定，B 可識別則 A 也可識別；反過來讀同樣的事實，A 不可判定則 B 也不可判定，A 不可識別則 B 也不可識別。由於「若且唯若」對稱地對待是與否，映射歸約也轉移共可識別性並尊重補集：A <=m B 與（A 的補集）<=m（B 的補集）是同一句話。這個對稱性正是為何要分離「可識別」與「不可識別」時，正確的工具是映射歸約，而非更強大的圖靈歸約。
要證明停機問題歸約到 A_TM（機器 M 是否接受輸入 w），就把停機問題的實例 (M, w) 映射成一對 (M', w)：建造 M' 模擬 M 在 w 上的執行，若 M 停機就讓 M' 接受。於是 M 在 w 上停機 若且唯若 M' 接受 w，所以 f(M, w) = (M', w) 是從 HALT 到 A_TM 的映射歸約。
一個可計算函數改寫問題，使「是」仍是「是」、「否」仍是「否」。
歸約函數 f 必須是全函數且永遠停機，而且等價關係必須雙向成立：w 屬於 A 若且唯若 f(w) 屬於 B。只把「是」方向做對的函數，並不是合法的映射歸約。