你的四個疑難點，追根究柢都繞著同一組概念打轉。先把這組概念的文法弄對，後面每一章都會輕鬆一半。

三個屬性：形容一個演算法

設 \(\mathcal{A}\) 是一個演算法（一台圖靈機），\(X\) 是一個判定問題。Week 10 教材給過三個屬性：

三個分類：形容一個問題

注意這些定義裡的量詞都是「存在」。一個問題永遠都有爛演算法（例如永遠回答 No 的機器：sound 或 complete 必有一個失守），這不影響分類；分類看的是最好情況下找不找得到夠好的演算法。

三件立刻要記住的事實：

1. 可判定 \(\Rightarrow\) C.E.（有 S\(+\)C\(+\)T 當然有 S\(+\)C），反之不然；

2. 「不可判定」\(\ne\)「毫無演算法」：\(\textsc{Halt}_{\mathrm{TM}}\) 不可判定，卻有 sound\(+\)complete 的演算法（下一章主角）；

3. SAT、TSP、CLIQUE 都是可判定的！它們只是（大概）很慢——NP-hard 說的是「多項式時間內大概解不了」，跟「有限時間內解不解得了」是兩個世界的問題。複雜度理論（Week 1–9）與可計算性理論（Week 10–11）的分界線就在這裡。

Week 10 疑問：停機問題有「Terminating」的屬性嗎？

先把問題問對

停機問題（Week 10 教材第 6 節）： \[\textsc{Halt}_{\mathrm{TM}}\;=\; \{\langle \mathrm{code}(M), w\rangle \;:\; M \text{ 在輸入 } w \text{ 上會停機}\}.\]

「\(\textsc{Halt}_{\mathrm{TM}}\) 有 Terminating 的屬性嗎？」——依第 1 章的文法，這句話犯了類別錯誤：Terminating 形容演算法，\(\textsc{Halt}_{\mathrm{TM}}\) 是問題。但這個疑問非常自然，因為它其實是三個合法問題疊在一起。把它們拆開，逐一回答：

混淆的根源：兩層「停機」

這個疑問之所以纏人，是因為題目裡有兩台機器、兩層停機，名字還撞在一起：

• 內層停機：被詢問的機器 \(M\) 在 \(w\) 上停不停——這是 \(\textsc{Halt}_{\mathrm{TM}}\) 的題目內容，是輸入資料的性質。

• 外層停機：解題的演算法 \(\mathcal{H}\) 對每個輸入 \(\langle\mathrm{code}(M),w\rangle\) 停不停——這才是 Terminating 屬性的所在。

不可判定性說的是：外層想永遠停機，就必須有辦法在有限時間內看穿內層的無限行為（「\(M\) 永遠不會停」是一個關於無限未來的斷言）。模擬只能忠實重播內層，內層不停、外層就跟著不停；而對角線論證證明了任何「不靠模擬的聰明捷徑」也一律不存在。

對角線證明三十秒複習

反設有 terminating 的判定器 \(H\)。造「唱反調機」\(D\)：輸入 \(\mathrm{code}(M)\)，問 \(H\)「\(M\) 吃自己的編碼會停嗎？」——\(H\) 說會停，\(D\) 就故意進入無窮迴圈；\(H\) 說不停，\(D\) 就立刻停。現在把 \(D\) 餵給自己：\(D(\mathrm{code}(D))\) 停 \(\Rightarrow\) 依定義它不停；不停 \(\Rightarrow\) 依定義它停。兩頭都矛盾，故 \(H\) 不存在。（結構同理髮師悖論：規則套到自己身上時自爆。）

注意這個證明用到了 \(H\) 的 terminating：\(D\) 必須等得到 \(H\) 的答覆才能唱反調。這再一次凸顯：被推翻的是「S\(+\)C\(+\)T 三者兼得」，而不是「S\(+\)C」——後者由模擬演算法安然實現。

Week 2 定義 5.2：多項式歸約 \(X\le_pY\)

動機：歸約是「難度的比較器」

我們常常無法直接算出一個問題「有多難」，但可以比較相對難度。日常版本：

把「先把輸入改寫一下，再呼叫另一個問題的求解器」這件事正式化，就是歸約。

定義的三個零件，各司其職

零件一：\(f\) 是「翻譯器」，不是「求解器」。

\(f\) 吃進 \(X\) 的實例 \(w\)，吐出 \(Y\) 的實例 \(f(w)\)。它全程不知道也不需要知道 \(w\) 的答案——它只負責改寫題目，讓「新題目在 \(Y\) 中的答案」恰好等於「舊題目在 \(X\) 中的答案」。真正回答問題的是後面 \(Y\) 的求解器：

答案原封不動照抄：\(Y\) 的求解器說 Yes 我們就答 Yes，說 No 就答 No。整個管線只呼叫 \(Y\) 一次、不翻轉答案——這是 \(\le_p\)（與 \(\le_m\)）的特徵。

零件二：「\(\iff\)」必須雙向。

\[\underbrace{w\in X \Rightarrow f(w)\in Y}_{\text{Yes 送到 Yes}} \qquad\text{且}\qquad \underbrace{w\notin X \Rightarrow f(w)\notin Y}_{\text{No 送到 No}}.\] 少了第二半，管線會壞掉：\(Y\) 的求解器對 \(f(w)\) 說 Yes 時，你無法分辨是「\(w\) 真的屬於 \(X\)」還是「\(f\) 把 No 實例亂丟進 \(Y\)」。

零件三：「多項式時間」防止翻譯器作弊。

若允許 \(f\) 花指數時間，\(f\) 可以自己暴力解掉 \(X\)：算出 \(w\) 的答案後，輸出 \(Y\) 的某個固定 Yes 或 No 實例。這樣的「歸約」什麼都沒比較——翻譯器把工作全做完了。限制 \(f\) 是多項式時間，翻譯器就買不起「先解再翻」，只能做結構上的忠實改寫；於是 \(X\le_pY\) 才真的意味著「\(Y\) 的求解能力被借用了」。

多項式的另一個好處是封閉性：多項式 \(\circ\) 多項式 \(=\) 多項式，所以：

一正一反：歸約的兩種用法

定理 3(b) 是「正著用」；把它取逆否就得到「反著用」——後者才是 NP 理論的日常：

NP-hard、NP-complete 與 Cook–Levin

「每一個 NP 問題」有無窮多個，不可能逐一歸約——這就是 Cook–Levin 定理（\(\textsc{Sat}\) 是 NP-complete）偉大的地方：它一次對付了全部（把任意 NP 機器的計算表編成布林公式）。此後要證 \(B\) 是 NP-hard，只需一條 \(\textsc{Sat}\le_pB\)（或任何已知 NP-complete 問題 \(\le_pB\)），再靠傳遞性收工。這是「反用」的制度化。

完整小例子：把定義的每個零件踩過一遍

玩具例（看格式）：\(X=\{\text{二進位偶數}\}\)，\(Y=\{\text{二進位奇數}\}\)。取 \(f(w)=w+1\)（二進位加法）。 （i）\(f\) 多項式時間可計算 ；（ii）\(w\) 是偶數 \(\iff w+1\) 是奇數  ——雙向成立。故 \(X\le_pY\)。雖然內容平凡，但考試論證歸約時要寫的就是這兩張支票：\(f\) 快、\(\iff\) 雙向。

課程主例（看實戰）：\(\textsc{Sat}\le_p\textsc{Clique}\)。給定 CNF 公式 \(F=C_1\land\cdots\land C_k\)，\(f\) 輸出圖 \(G_F\) 與整數 \(k\)：每個子句的每個文字出現當一個頂點；兩頂點連邊 \(\iff\) 不同子句且不互為否定（\(X\) 與 \(\lnot X\)）。 （i）\(f\) 只是逐對檢查文字、畫 \(O((nk)^2)\) 條邊——多項式 ；（ii）\(F\) 可滿足 \(\iff G_F\) 有 \(k\)-團——雙向論證正是 Exercises 第二部分 Q3 與本教材模板 B（第 5.2 節）的內容。

常見誤解清單

Week 11：映射歸約 \(A\le_mB\)，與 \(\le_p\) 的對照

定義：把 \(\le_p\) 的「多項式」放寬成「可計算」

跟定義 2 逐字比對，唯一的差別是對 \(f\) 的資源要求：\(\le_p\) 要求多項式時間，\(\le_m\) 只要求「算得出來」（有限時間即可，多慢都行）。為什麼可以放寬？因為兩套理論關心的貨幣不同：

在可計算性的世界裡，「多項式 vs 指數」的差別根本不入帳——那裡的敵人是無限（不停機），不是很慢。所以把 \(f\) 的門檻降到可計算即可；相對地，結論也從「P 裡外」升級成「可判定與否、C.E. 與否」。

基本定理與實戰形式

實戰一：\(\textsc{Halt}_{\mathrm{TM}}\le_mA_{\mathrm{TM}}\)（「拒絕改接受」）

目標：已知 \(\textsc{Halt}_{\mathrm{TM}}\) 不可判定，證明接受問題 \(A_{\mathrm{TM}}=\{\langle\mathrm{code}(M),w\rangle : M \text{ 接受 } w\}\) 不可判定。要造可計算的 \(f\) 使 \(\langle\mathrm{code}(M),w\rangle\in\textsc{Halt}_{\mathrm{TM}}\iff f(\langle\mathrm{code}(M),w\rangle)\in A_{\mathrm{TM}}\)。

改造機器：對任意 \(M\)，建構 \(M'\)——把 \(M\) 的拒絕出口改接到接受：

於是 \(M'\) 接受 \(w\) \(\iff\) \(M\) 在 \(w\) 上停機（不論停成接受還是拒絕）；\(M\) 不停則 \(M'\) 也不停（不接受）。

歸約函數：\(f(\langle\mathrm{code}(M),w\rangle) = \langle\mathrm{code}(M'),w\rangle\)。\(f\) 只做語法改寫（把轉移表中指向 \(q_{\mathrm{reject}}\) 的箭頭改指 \(q_{\mathrm{accept}}\)），顯然可計算。雙向等價： \[\langle\mathrm{code}(M),w\rangle\in\textsc{Halt}_{\mathrm{TM}}\iff M' \text{ 接受 } w \iff \langle\mathrm{code}(M'),w\rangle\in A_{\mathrm{TM}}.\] 由推論 7，\(A_{\mathrm{TM}}\) 不可判定。\(\blacksquare\)

實戰二：\(A_{\mathrm{TM}}\le_m\overline{E}_{\mathrm{TM}}\)（「寫死輸入」——歸約的萬用招）

目標：證明非空問題 \(\overline{E}_{\mathrm{TM}}=\{\mathrm{code}(M) : L(M)\ne\emptyset\}\) 不可判定。注意兩邊的實例形狀不同：\(A_{\mathrm{TM}}\) 的實例是「一對」\(\langle\mathrm{code}(M),w\rangle\)，\(\overline{E}_{\mathrm{TM}}\) 的實例是「一台機器」。\(f\) 要把一對變一台——方法是把 \(w\) 燒進程式：

\(M_w\) 無視自己的輸入 \(u\)，永遠模擬同一件事 \(M(w)\)。所以它的語言只有兩個極端： \[L(M_w)= \begin{cases} \Sigma^{*} & \text{若 } M \text{ 接受 } w \quad(\text{每個 } u \text{ 都被接受})\\ \emptyset & \text{否則} \quad(\text{沒有任何 } u \text{ 被接受}) \end{cases} \qquad\Longrightarrow\qquad L(M_w)\ne\emptyset \iff M \text{ 接受 } w.\]

歸約函數：\(f(\langle\mathrm{code}(M),w\rangle)=\mathrm{code}(M_w)\)。\(f\) 可計算：把「清空磁帶、抄入常數 \(w\)」這段固定程式接在 \(M\) 的程式前面——純語法組裝，不需執行 \(M\)。雙向等價如上。由推論 7，\(\overline{E}_{\mathrm{TM}}\) 不可判定；再由「可判定性對補集封閉」，\(E_{\mathrm{TM}}\) 也不可判定。\(\blacksquare\)

考場上的歸約題怎麼寫：五步驟

Exercises 第二部分 Q1／Q3／Q11：三個可遷移的作答模板

這三題卡住的感覺通常不是「算不出來」，而是「不知道這種題目標準答案長什麼樣子」。好消息：它們分別代表三種題型，每種都有固定的作答骨架，而且 2019／2020 年真題各有一題可以直接套。共同心法先講在前面：

模板 A（Q1 型）：證明問題屬於 NP——「猜、驗、對、快」

四步骨架。

1. 猜（Guess，非確定性步驟）：非確定性地產生一個「候選解」（＝證書）。說清楚猜的物件是什麼、長度為何是輸入的多項式。

2. 驗（Verify，確定性步驟）：在單一分支內，用普通的確定性程序檢查候選解是否真的是解。列出檢查的每一項。

3. 對（正確性，兩句話）：Yes 實例 \(\Rightarrow\) 存在某分支猜中真的解並通過驗證（完備）；No 實例 \(\Rightarrow\) 沒有任何候選解能通過驗證，所有分支拒絕（健全）。

4. 快（時間分析）：只需論證「每一條分支」是多項式時間——猜的步數 \(+\) 驗的步數。分支總數可以是指數（\(2^n\) 條），完全沒關係；NP 的定義只管單一分支的深度，不管樹有多寬。

示範作答（Q1 原題：\(\textsc{Subset-Sum}\in\) NP）。

輸入：整數集 \(S=\{a_1,\dots,a_n\}\) 與目標 \(k\)。

1. 猜：對每個 \(i=1,\dots,n\) 非確定性地決定「\(a_i\) 放不放進 \(S'\)」——\(n\) 個二選一，產生候選子集 \(S'\)（證書長度 \(n\) 位元）。

2. 驗：計算 \(\sum_{a\in S'}a\)（至多 \(n\) 次加法），檢查是否等於 \(k\)；相等則接受，否則本分支拒絕。

3. 對：若存在和為 \(k\) 的子集，「恰好猜中它」的那條分支會接受（完備）；若不存在，每條分支的和都 \(\ne k\)，全部拒絕（健全）。

4. 快：每條分支做 \(n\) 次選擇、\(n\) 次加法、一次比較；整數以 \(m\) 位元計，單分支 \(O(nm)\)——輸入長度的多項式。\(\blacksquare\)

遷移到真題。

同一骨架，只換「猜什麼、驗什麼」：

模板 B（Q3 型）：解釋歸約為什麼正確——「恰取一、不矛盾、可指派、全滿足」

背景（三十秒回顧建圖規則）。

\(\textsc{Sat}\le_p\textsc{Clique}\) 的圖 \(G_F\)：每個子句的每個文字出現＝一個頂點；連邊 \(\iff\)（i）不同子句且（ii）不互為否定。\(k=\) 子句數。兩條「禁止連邊」的規則，等一下每條各變成論證的一步——這是這類題的通用心法：把建構規則逐條翻譯成論證步驟。

四步骨架（「\(k\)-團 \(\Rightarrow\) 滿足指派」方向）。

1. 恰取一：同子句內部無邊（規則 i），而團要求兩兩相鄰 \(\Rightarrow\) 團中沒有兩個頂點同子句；團有 \(k\) 個頂點、圖恰有 \(k\) 個子句 \(\Rightarrow\) 由鴿籠原理，每個子句恰貢獻一個頂點。

2. 不矛盾：互為否定的文字之間無邊（規則 ii）\(\Rightarrow\) 團中不可能同時出現 \(X\) 與 \(\lnot X\)。

3. 可指派：把團中文字統統設為真——\(X\in C\) 令 \(X=\)True、\(\lnot X\in C\) 令 \(X=\)False，未提及的變數任意。由第 2 步，同一變數不會收到矛盾指令 \(\Rightarrow\) 指派良定義。

4. 全滿足：由第 1 步，每個子句都有一個文字被設為真；子句是析取（or），一真則句真 \(\Rightarrow\) \(k\) 個子句全真 \(\Rightarrow\) \(F\) 為真。\(\blacksquare\)

把骨架「看」出來。

下圖是 Exercises Q2/Q3 的九頂點圖（\(F=(P\lor\lnot Q\lor R)\land(P\lor Q\lor\lnot R)\land(\lnot P\lor Q\lor R)\)），紅色粗邊是一個 3-團 \(\{P_{c_1},\,Q_{c_2},\,R_{c_3}\}\)：

紅色團一子句一頂點（恰取一 ）、沒有互否對（不矛盾 ）\(\Rightarrow\) 指派 \(P=Q=R=\)True（可指派 ）\(\Rightarrow\) 三個子句分別靠 \(P\)、\(Q\)、\(R\) 為真（全滿足 ）。四步在圖上一眼看完。

反方向（「可滿足 \(\Rightarrow\) 有 \(k\)-團」）也備著。

考題若問另一個方向（歸約完整證明需要雙向）：設 \(\sigma\) 是滿足指派，每個子句至少有一個真文字，各挑一個，得 \(k\) 個頂點。它們兩兩相鄰：跨不同子句（規則 i 通過）；且同時為真的文字不可能互為否定（規則 ii 通過）。故構成 \(k\)-團。——注意論證恰好把兩條建圖規則再各用一次。

模板 C（Q11 型）：近似性定義題——「存在、上界、對所有」

定義三件套。

以最小化問題為例，「\(X\) 是 \(r\)-approximable（\(r\ge 1\)）」的標準答案由三個零件組成，一件都不能少：

示範作答（Q11 原題：Metric TSP 是 2-approximable）。

「存在一個多項式時間的演算法 \(\mathcal{A}\)，使得對 Metric TSP 的每一個實例 \(I\)，\(\mathcal{A}\) 回傳一條合法路線，其長度至多是該實例最佳路線長度的兩倍：\(\mathrm{cost}(\mathcal{A}(I))\le 2\cdot\mathrm{OPT}(I)\)。」

三件套逐一到位： 存在＋多項式時間、 \(\le 2\cdot\mathrm{OPT}\)、 每一個實例。若題目再問「為什麼做得到」，補 MST 三步（MST \(\le\mathrm{OPT}\)；沿樹來回走 \(\le 2\cdot\)MST；三角不等式保證抄捷徑不變長）。

變體一（2019 Q8，\(r\)-approximable 選擇題）。

四個選項各踩壞一個零件：A「不存在多項式精確演算法」——答非所問（那是難度敘述，不是近似保證）；B「\(r\) 次疊代後回傳最佳解」——把 \(r\) 誤當疊代次數，踩壞 ；C「每個演算法的近似比都 \(\ge r\)」——量詞方向全反（那是不可近似下界），踩壞 ；D 正確。用三件套當檢查表，選擇題變成核對題。

變體二（2020 Q6，unapproximable）。

「不可近似」就是對定義做全稱否定： \[\text{對\emph{每一個}固定 } r\ge 1\text{：都\emph{不存在}近似比 } r \text{ 的多項式時間演算法（假設 P}\ne\text{NP）。}\] 注意否定後量詞翻轉：「存在一個 \(r\) 使……」是不夠格的答案。經典例子：一般（非 Metric）TSP unapproximable——若有任何常數比近似，就能多項式時間解 \(\textsc{HamCycle}\)，逼出 P\(=\)NP。

三個模板的合影

速查表與自我測驗

一頁速查表

自我測驗（八題）

1. 「停機問題是 terminating 的」這句話哪裡有毛病？把它改寫成一個合法且答案為「否」的問題、以及一個合法且答案為「是」的問題。

2. 為什麼「用萬能圖靈機模擬 \(M(w)\)」證明了 \(\textsc{Halt}_{\mathrm{TM}}\) 是 C.E.，卻證明不了 \(\textsc{Halt}_{\mathrm{TM}}\) 可判定？

3. 定義 \(X\le_pY\) 的三個零件是什麼？各防什麼弊？

4. 你的同學寫道：「\(B\le_p\textsc{Sat}\)，而 \(\textsc{Sat}\) 是 NP-complete，所以 \(B\) 是 NP-hard。」哪裡錯了？

5. \(\le_m\) 與 \(\le_p\) 唯一的定義差別是什麼？為什麼可計算性理論不需要「多項式」？

6. 用「寫死輸入」造出的 \(M_w\)，它的語言為什麼只有 \(\Sigma^*\) 與 \(\emptyset\) 兩種可能？這件事在 \(A_{\mathrm{TM}}\le_m\overline{E}_{\mathrm{TM}}\) 中扮演什麼角色？

7. 用模板 A 證明 \(\textsc{Clique}\in\) NP（四步都要寫）。

8. 「Metric TSP 是 2-approximable」與「一般 TSP 是 unapproximable」，兩句話的量詞結構各是什麼？

參考解答提示

1. 類別錯誤：terminating 形容演算法。合法問題（答案否）：「存在 S\(+\)C\(+\)T 的演算法判定 \(\textsc{Halt}_{\mathrm{TM}}\) 嗎？」（不可判定）。合法問題（答案是）：「存在 S\(+\)C 的演算法辨識 \(\textsc{Halt}_{\mathrm{TM}}\) 嗎？」（模擬；C.E.）。

2. 模擬對 Yes 實例有限步內回答，故 sound \(+\) complete；但對「\(M\) 不停」的輸入自己也不停，不 terminating——而可判定需要三者兼備。

3. \(f\) 是翻譯器（不解題）；雙向 \(\iff\)（單向無資訊量，見固定 Yes 實例反例）；\(f\) 多項式（防「先解再翻」、保證合成封閉）。

4. 方向反了。\(B\le_p\textsc{Sat}\) 只說明 \(B\) 不比 \(\textsc{Sat}\) 難（NP 中人人如此）。要證 \(B\) 是 NP-hard 需要 \(\textsc{Sat}\le_pB\)。

5. \(\le_p\) 要求 \(f\) 多項式時間、\(\le_m\) 只要求可計算。可計算性理論的敵人是「不停機」而非「很慢」，故資源門檻只需「有限時間」。

6. \(M_w\) 無視輸入，行為與輸入無關：要嘛全接受（\(M\) 接受 \(w\)）要嘛全不接受。於是「\(L(M_w)\ne\emptyset\)」與「\(M\) 接受 \(w\)」畫上等號——把「一對」的問題翻譯成「一台機器」的問題。

7. 猜：非確定性選 \(k\) 個頂點（證書 \(O(k\log n)\) 位元）；驗：檢查 \(\binom{k}{2}\) 對是否皆相鄰；對：有 \(k\)-團則猜中的分支接受、無則全拒絕；快：單分支 \(O(n^2)\) 次查邊。

8. 前者：存在一個多項式演算法，對所有實例回傳 \(\le 2\cdot\mathrm{OPT}\)。後者（全稱否定）：對每個固定 \(r\ge1\)，不存在多項式 \(r\)-近似演算法（假設 P\(\ne\)NP）。

參考資料

1. 本課程教材：Week 2〈P 與 NP〉（定義 5.1–5.2、引理 5.3）、Week 10〈學習教材〉第 3、6 節、Week 11〈可計算枚舉與映射歸約〉。

2. 本課程 Exercises 詳解：第二部分 Q1、Q2、Q3、Q11。

3. 歷屆試題：5CCS2FC2 January 2019（Q1, Q2, Q8, Q11, Q12c, Q13）、January 2020（Q1, Q2, Q6, Q11, Q13）及本資料夾內對應詳解。

4. M. Sipser, Introduction to the Theory of Computation, 3rd ed.（第 4、5、7 章）。

5. J. Kleinberg, É. Tardos, Algorithm Design（第 8 章：多項式歸約）。