遞迴可枚舉（Recursively Enumerable）的定義 [4 分]

題目說明

本題考三個核心性質的定義。設演算法 \(\mathcal{A}\) 針對判定問題 \(X\)：

• Sound（可靠）：若 \(\mathcal{A}\) 回答「是」，則輸入真的屬於 \(X\)（不誤報）；

• Complete（完備）：對每個屬於 \(X\) 的輸入，\(\mathcal{A}\) 都會回答「是」（不漏報）；

• Terminating（終止）：\(\mathcal{A}\) 對所有輸入都在有限步內停止。

課程定義：\(X\) 可判定 \(\iff\) 存在 sound + complete + terminating 的演算法；\(X\) 遞迴可枚舉 \(\iff\) 存在 sound + complete 的演算法（不要求終止），即擁有「半判定程序」。

詳細解答

• A. 這是「\(X\) 不可判定」的敘述，不是 r.e. 的定義。而且 r.e. 的問題也可能可判定（可判定 \(\Rightarrow\) r.e.），此時 A 為假。錯誤。

• B. 若 \(\overline{X}\) 可判定則 \(X\) 也可判定（把答案反過來即可），這比 r.e. 強得多；且存在 r.e. 但補問題不可判定的例子（如停機問題）。錯誤。

• C. 補問題是否 r.e. 與 \(X\) 本身是否 r.e. 是獨立的性質：可判定的 \(X\) 是 r.e. 且 \(\overline{X}\) 也是 r.e.，此時 C 為假。錯誤。

• D. 「存在 sound 且 complete 的演算法」正是 r.e. 的定義。正確。

• E. 因 D 正確，排除。

映射歸約（Mapping Reduction）的條件 [6 分]

題目說明

詳細解答

映射歸約的標準定義：\(f : \Sigma^{*} \to \Sigma^{*}\) 是從 \(X\) 到 \(Y\) 的映射歸約，若

1. \(f\) 是可計算函數（存在圖靈機對每個輸入 \(w\) 都能停機並輸出 \(f(w)\)）；

2. 對所有 \(w \in \Sigma^{*}\)：\(w \in X \iff f(w) \in Y\)（雙向保持答案：yes 對應 yes、no 對應 no）。

逐一檢視選項：

• A. 條件寫錯了：左邊應該是 \(w \in X\) 而不是 \(f(w) \in X\)。「\(f(w) \in X \iff f(w) \in Y\)」是關於輸出字串同時屬於兩個語言的怪異條件，與歸約無關。錯誤。

• B. 正是定義中的第 2 個條件。正確。

• C. 「多項式時間可計算」是多項式歸約 \(\le_p\)（用於 NP-completeness）的額外要求；一般的映射歸約（用於可計算性理論）只要求可計算，不要求多項式。錯誤。

• D. 正是定義中的第 1 個條件。若 \(f\) 不可計算，歸約就毫無用處（無法把「解 \(Y\) 的程序」轉成「解 \(X\) 的程序」）。正確。

• E. 映射歸約對任何一對語言都可以定義，與 \(X\) 是否可判定無關（例如可判定問題之間也常做歸約）。錯誤。

Master 定理：判斷 \(\Theta(n^{2}\log n)\) [6 分]

題目說明

詳細解答

選項 A： \(a=4\), \(b=2\)，\(c^{*}=\log_2 4 = 2\)。\(f(n)=n\log_2 n\)。因為 \(\log n\) 成長慢於任何正冪次，\(n\log_2 n = O(n^{2-\varepsilon})\)（取 \(\varepsilon=0.5\)），屬 Case 1： \[T(n) = \Theta(n^{2}) \ne \Theta(n^{2}\log n).\quad\text{不符。}\]

選項 B： \(a=4\), \(b=2\)，\(c^{*}=2\)。\(f(n)=n^{2}\log_2 n\)。此函數恰好卡在縫隙：它不是 \(O(n^{2-\varepsilon})\)、不是 \(\Theta(n^{2})\)、也不是 \(\Omega(n^{2+\varepsilon})\)（\(\log n\) 比任何 \(n^{\varepsilon}\) 都慢），基本型 Master 定理三個 case 都不適用。用加強版（\(f(n)=\Theta(n^{c^{*}}\log^{k} n)\) 時 \(T(n)=\Theta(n^{c^{*}}\log^{k+1} n)\)，此處 \(k=1\)）可得 \[T(n) = \Theta(n^{2}\log^{2} n) \ne \Theta(n^{2}\log n).\quad\text{不符。}\]

選項 C： \(a=9\), \(b=3\)，\(c^{*}=\log_3 9 = 2\)。\(f(n) = n(n+1) = n^{2}+n = \Theta(n^{2})\)，恰等於臨界冪次，屬 Case 2： \[T(n) = \Theta(n^{2}\log n).\quad\textbf{符合。}\]

選項 D： \(a=2\), \(b=4\)，\(c^{*}=\log_4 2 = \tfrac12\)。\(f(n)=3n^{2} = \Omega(n^{1/2+\varepsilon})\)，檢查正則條件： \[a\,f(n/b) = 2\cdot 3\left(\frac{n}{4}\right)^{2} = \frac{3}{8}n^{2} = \frac{1}{8}\cdot 3n^{2} \le c\,f(n),\quad c = \tfrac18 < 1.\;\checkmark\] 屬 Case 3：\(T(n) = \Theta(n^{2}) \ne \Theta(n^{2}\log n)\)。不符。

2SAT 蘊涵圖的強連通分量個數 [3 分]

題目說明

詳細解答

步驟一：由每個子句寫出兩條蘊涵邊。 \[\begin{array}{lll} (P \lor Q): & \lnot P \rightarrow Q, & \lnot Q \rightarrow P\\[1pt] (P \lor \lnot S): & \lnot P \rightarrow \lnot S, & S \rightarrow P\\[1pt] (\lnot P \lor \lnot R): & P \rightarrow \lnot R, & R \rightarrow \lnot P\\[1pt] (R \lor Q): & \lnot R \rightarrow Q, & \lnot Q \rightarrow R\\[1pt] (R \lor S): & \lnot R \rightarrow S, & \lnot S \rightarrow R \end{array}\]

步驟二：畫出蘊涵圖。（8 個節點、10 條邊）

步驟三：找出強連通分量。

• 迴圈 \(P \rightarrow \lnot R \rightarrow S \rightarrow P\)：\(\{P,\, \lnot R,\, S\}\) 互相可達，構成一個 SCC。

• 鏡像迴圈 \(\lnot P \rightarrow \lnot S \rightarrow R \rightarrow \lnot P\)：\(\{\lnot P,\, \lnot S,\, R\}\) 構成一個 SCC（2SAT 蘊涵圖的對偶對稱性）。

• \(Q\) 沒有任何出邊（\(Q\) 只出現在子句的正文字位置，其蘊涵都指向 \(Q\)），到不了任何點，故 \(\{Q\}\) 自成單點 SCC。

• \(\lnot Q\) 沒有任何入邊（沒有蘊涵以 \(\lnot Q\) 為終點），沒有點能回到它，故 \(\{\lnot Q\}\) 自成單點 SCC。

共 \(\{P, \lnot R, S\}\)、\(\{\lnot P, \lnot S, R\}\)、\(\{Q\}\)、\(\{\lnot Q\}\) 四個 SCC。

（附帶一提：沒有任何變數與其否定同處一個 SCC，故此公式可滿足；例如 \(P = \text{True}, R = \text{False}, S = \text{True}, Q = \text{True}\)。）

2SAT 可滿足性的充要條件 [3 分]

題目說明

詳細解答

標準判準（Aspvall–Plass–Tarjan 定理）： \[\text{2SAT 可滿足} \iff \text{沒有任何變數 } X \text{ 使 } X \text{ 與 } \lnot X \text{ 落在同一個 SCC 中。}\] 而「\(X\) 與 \(\lnot X\) 在同一個 SCC」\(\iff\)「存在一條同時經過 \(X\) 與 \(\lnot X\) 的迴圈」（互相可達即可沿 \(X \rightsquigarrow \lnot X \rightsquigarrow X\) 繞一圈）。因此選項 C 與標準判準等價。

逐一檢視：

• A. 太強了，只是充分條件而非必要。單向路徑 \(X \rightsquigarrow \lnot X\) 是允許的——它只是強迫 \(X\) 必須為假。例如公式 \((\lnot X \lor \lnot X)\) 給出邊 \(X \to \lnot X\)，公式可滿足（\(X\) 取假），但 A 的條件不成立。錯誤。

• B. 既不必要也不充分。第 4 題的 SCC \(\{P, \lnot R, S\}\) 混合了正負文字，而該公式可滿足——不必要。錯誤。

• C. 「沒有迴圈同時含 \(X\) 與 \(\lnot X\)」\(\iff\)「\(X\) 與 \(\lnot X\) 不同 SCC（對所有 \(X\)）」\(\iff\) 可滿足。充要，正確。

• D. 空集合本來就不會是強連通分量（SCC 是非空的極大集合），此條件恆真，對任何公式都成立，不能區分可滿足與否。錯誤。

不可近似（Unapproximable）的定義 [4 分]

題目說明

詳細解答

回顧定義：\(X\) 是 \(r\)-approximable，若存在多項式時間演算法回傳的解保證不劣於最佳解的 \(r\) 倍。「unapproximable」是它的全稱否定： \[\text{對\emph{每一個}固定常數 } r \ge 1\text{，}X \text{ 都\emph{不是} } r\text{-approximable。}\] 也就是說，除非 \(\mathrm{P} = \mathrm{NP}\)，任何多項式時間演算法都無法給出任何常數倍品質保證。經典例子：一般（不滿足三角不等式的）TSP 就是 unapproximable——若它有任何常數比的近似演算法，就能用來在多項式時間內解 Hamiltonian Cycle，導致 \(\mathrm{P} = \mathrm{NP}\)。

逐一檢視：

• A. 把 \(r\) 誤解為「疊代次數」；\(r\) 是解品質的倍率，且此敘述與近似性無關。錯誤。

• B. 近似比依定義 \(\ge 1\)（\(r=1\) 表示精確最佳）；\(r<1\) 表示「比最佳解更好」，不可能。錯誤。

• C. 正是 unapproximable 的定義。正確。

• D. 混淆了「計算困難（NP-hard）」與「不可判定」。NP 最佳化問題的判定版本都是可判定的（窮舉即可），只是慢。錯誤。

單體法（Simplex Method）的一次疊代 [7 分]

題目說明

詳細解答

步驟一：選樞軸行（entering variable）。目標函數列為 \((-3,\; 1,\; 0,\; 0,\; 0)\)，唯一的負係數是 \(x\) 行的 \(-3\)，故選 。

步驟二：比值測試（ratio test）。對樞軸行中為正的元素計算「右端值 \(\div\) 該元素」，取最小的非負比值： \[\begin{array}{c|c|c|l} \text{列} & x \text{ 行元素} & \text{比值} & \text{判斷}\\ \hline 1 & 7 & -8/7 \approx -1.14 & \text{比值為負，不考慮}\\ 2 & 1 & 5/1 = 5 & \text{候選（最小）}\\ 3 & 1 & 9/1 = 9 & \text{候選} \end{array}\] 最小非負比值在第 2 列，故樞軸元素為第 2 列 \(x\) 行的 \(1\)。

步驟三：樞軸列正規化。樞軸元素已是 \(1\)，不需縮放： \[R_2' = \bigl(1,\; -8,\; 0,\; 1,\; 0,\; 0 \bigm| 5\bigr).\]

步驟四：消去其他列的 \(x\) 行。 \[\begin{align*} R_1' &= R_1 - 7R_2' = \bigl(7-7,\; 3+56,\; 1,\; -7,\; 0,\; 0 \bigm| -8-35\bigr) = \bigl(0,\; 59,\; 1,\; -7,\; 0,\; 0 \bigm| -43\bigr),\\ R_3' &= R_3 - R_2' = \bigl(0,\; -7+8,\; 0,\; -1,\; 1,\; 0 \bigm| 9-5\bigr) = \bigl(0,\; 1,\; 0,\; -1,\; 1,\; 0 \bigm| 4\bigr),\\ R_4' &= R_4 + 3R_2' = \bigl(-3+3,\; 1-24,\; 0,\; 3,\; 0,\; 1 \bigm| 0+15\bigr) = \bigl(0,\; -23,\; 0,\; 3,\; 0,\; 1 \bigm| 15\bigr). \end{align*}\]

步驟五：寫出 \(T_2\) 並讀取指定位置。 \[T_2 = \quad \begin{array}{|cccccc|c|} \hline x & y & s_1 & s_2 & s_3 & C & \\ \hline 0 & 59 & 1 & \fbox{$-7$} & 0 & 0 & -43\\ \fbox{1} & -8 & 0 & 1 & 0 & 0 & 5\\ 0 & 1 & 0 & -1 & 1 & 0 & \fbox{4}\\ \hline 0 & \fbox{$-23$} & 0 & 3 & 0 & 1 & 15\\ \hline \end{array}\] \(Z\)（第 1 列 \(s_2\) 行）\(= -7\)；\(X\)（第 2 列 \(x\) 行）\(= 1\)；\(W\)（第 3 列右端）\(= 4\)；\(Y\)（第 4 列 \(y\) 行）\(= -23\)。

TSP：2-opt 疊代至局部最小 [6 分]

題目說明

詳細解答

權重表： \[\begin{array}{c|ccccc} & A & B & C & D & E\\ \hline A & - & 7 & 12 & 10 & 22\\ B & 7 & - & 6 & 23 & 8\\ C & 12 & 6 & - & 17 & 11\\ D & 10 & 23 & 17 & - & 26\\ E & 22 & 8 & 11 & 26 & - \end{array}\] 目前路線 \(A \to C \to B \to E \to D \to A\)：\(12+6+8+26+10 = 62\)。

第一輪：檢查目前路線（62）的全部 5 個 2-opt 鄰居。每個交換「移除兩條邊、加入兩條邊」的淨變化為 \(\Delta = (\text{新邊和}) - (\text{舊邊和})\)：

唯一能改善的交換是第一列：第 1 次套用，得到新路線 \(A \to B \to C \to E \to D \to A\)，長度 \(60\)。

第二輪：檢查路線（60）的 5 個鄰居。

唯一能改善的交換是第三列：第 2 次套用，得到 \(A \to B \to E \to C \to D \to A\)，長度 \(53\)。

第三輪：檢查路線（53）的 5 個鄰居。 \[\begin{array}{ll} \text{移除 } (A,B),(E,C) \Rightarrow 63; & \text{移除 } (A,B),(C,D) \Rightarrow 64;\\ \text{移除 } (B,E),(C,D) \Rightarrow 60; & \text{移除 } (B,E),(D,A) \Rightarrow 78;\\ \text{移除 } (E,C),(D,A) \Rightarrow 70. & \end{array}\] 所有鄰居都 \(\ge 53\)，沒有任何改善交換，已抵達局部最小（事實上 53 也是全域最佳解）。

結論：\(62 \xrightarrow{\text{第 1 次}} 60 \xrightarrow{\text{第 2 次}} 53\)（停止）。共需 2 次 2-opt 交換。由於每一輪的改善交換都是唯一的，這個次數與交換的選取策略無關。

SCC 演算法：最後找到的強連通分量 [6 分]

題目說明

詳細解答

步驟一：先確定 SCC 的劃分（沿有向迴圈找互相可達的集合）：

• \(A \to F \to C \to A\)：\(S_1 = \{A, C, F\}\)；

• \(C \to M\)，而 \(M\) 沒有任何路徑回到 \(C\)：\(S_2 = \{M\}\)；

• \(E \to H\) 與 \(H \to E\)：\(S_3 = \{E, H\}\)；

• \(G \to L \to I \to G\)：\(S_4 = \{G, I, L\}\)；

• \(B \to N \to D \to Q \to P \to O \to B\)：\(S_5 = \{B, D, N, O, P, Q\}\)。

共 5 個 SCC（\(3+1+2+3+6 = 15\) 個節點 ）。

步驟二：模擬演算法（節點選取採字母順序）。第一趟在 \(G\) 上做 DFS（從 \(A\) 出發），完成順序為 \[O,\; P,\; Q,\; D,\; N,\; B,\; I,\; L,\; G,\; H,\; E,\; M,\; C,\; F,\; A,\] 故清單（完成得越晚排越前面）為 \[L = \langle A,\; F,\; C,\; M,\; E,\; H,\; G,\; L,\; I,\; B,\; N,\; D,\; Q,\; P,\; O\rangle.\]

步驟三：依序在轉置圖 \(G^{T}\) 上做 DFS。

1. 取 \(A\)：\(G^{T}\) 中 \(A \leftarrow C \leftarrow F \leftarrow A\)，找到 \(\mathbf{S_1 = \{A, C, F\}}\)；

2. 取 \(M\)：\(M\) 在 \(G^{T}\) 中唯一的鄰居 \(C\) 已歸類，找到 \(\mathbf{S_2 = \{M\}}\)；

3. 取 \(E\)：\(E \leftrightarrow H\)，找到 \(\mathbf{S_3 = \{E, H\}}\)；

4. 取 \(G\)：\(G \leftarrow I \leftarrow L \leftarrow G\)，找到 \(\mathbf{S_4 = \{G, I, L\}}\)；

5. 取 \(B\)：沿 \(G^{T}\) 走遍 \(B, O, P, Q, D, N\)，找到 \(\mathbf{S_5 = \{B, D, N, O, P, Q\}}\)。（最後）

為什麼答案不依賴節點選取順序？元件圖如下：

演算法輸出 SCC 的順序必為元件圖的拓撲順序，而 \(S_5\) 是元件圖中唯一的匯點（沒有出邊：\(S_5\) 內的 \(B, D, N, O, P, Q\) 的所有出邊都留在 \(S_5\) 內部），因此不論 DFS 的起點與鄰居順序如何選，\(S_5 = \{B, D, N, O, P, Q\}\) 必定是最後被找到的 SCC。

Prim 演算法：邊 \((E,G)\) 在第幾步加入 [5 分]

題目說明

詳細解答

全部 14 條邊： \(AB{=}5,\; AC{=}7,\; BE{=}8,\; CD{=}1,\; CF{=}4,\; DE{=}8,\; DF{=}7,\; EG{=}1,\; EH{=}3,\; FI{=}2,\; GI{=}5,\; GJ{=}6,\; HJ{=}7,\; IJ{=}10\)。

從 \(A\) 開始逐步執行（每步列出所有跨越邊，粗體為選中的最小者）：

說明幾個關鍵步驟：

• 第 3 步起 \(CD{=}1\) 是全場最小的跨越邊，優先於 \(BE(8)\)；

• 第 5、6 步沿著下排 \(F \to I \to G\) 便宜地擴張（\(2\) 與 \(5\) 都小於 \(8\)）；

• 第 7 步：\(G\) 進入樹後，\(EG{=}1\) 成為新的跨越邊且是目前最小者，此時才把 \(E\) 拉進樹——邊 \((E, G)\) 於第 7 步加入；

• 每一步的最小跨越邊都是唯一的，因此答案不受平手規則影響。

（檢驗：MST 邊為 \(AB, AC, CD, CF, FI, GI, EG, EH, GJ\)，共 9 條，總權重 \(5{+}7{+}1{+}4{+}2{+}5{+}1{+}3{+}6 = 34\)。）

第二部分：長答題（第 11–13 題，任選兩題，每題 25 分）

\(E_{TM}\) 的不可判定性與遞迴可枚舉性 [25 分]

題目說明

(a) 映射歸約 \(A_{TM} \le_m E_{TM}\)（13 分）

歸約函數的建構。定義 \(f\)：給定輸入 \(\langle M, w\rangle\)，輸出一台新圖靈機的編碼 \(\langle M_w\rangle\)，其中 \(M_w\) 的行為如下：

\(f\) 是可計算的。\(f\) 只做語法上的組裝：把 \(M\) 的程式碼與常數字串 \(w\) 嵌進一個固定模板（「忽略輸入、模擬 \(M\) 於 \(w\)」）。這不需要執行 \(M\)，只是文字替換，顯然有圖靈機能對每個輸入 \(\langle M, w\rangle\) 在有限時間內輸出 \(\langle M_w\rangle\)。

答案的雙向保持。分析 \(M_w\) 的語言： \[L(M_w) = \begin{cases} \Sigma^{*}, & \text{若 } M \text{ 接受 } w \quad(\text{每個 } x \text{ 都被接受}),\\ \emptyset, & \text{若 } M \text{ 不接受 } w \quad(\text{沒有任何 } x \text{ 被接受}). \end{cases}\] 因此 \[\langle M, w\rangle \in A_{TM} \;\iff\; L(M_w) = \Sigma^{*} \ne \emptyset \;\iff\; \langle M_w\rangle \in E_{TM}. \checkmark\] 兩個條件都滿足，\(f\) 是從 \(A_{TM}\) 到 \(E_{TM}\) 的映射歸約，即 \(A_{TM} \le_m E_{TM}\)。

導出不可判定性。反設 \(E_{TM}\) 可判定，設 \(R\) 是其總是停機的判定器。則以下程序判定 \(A_{TM}\)：輸入 \(\langle M, w\rangle\)，計算 \(f(\langle M, w\rangle) = \langle M_w\rangle\)（有限時間），執行 \(R(\langle M_w\rangle)\) 並回傳其答案。此程序 sound、complete 且終止，即 \(A_{TM}\) 可判定——與已知的 \(A_{TM}\) 不可判定矛盾。

\[\therefore\; E_{TM} \text{ 不可判定。}\qquad\blacksquare\]

(b) 遞迴可枚舉性：交錯模擬（7 分）

難點：要判斷 \(L(M) \ne \emptyset\) 得「找到一個被接受的字串」，但我們既不知道是哪個字串，也不知道要模擬多少步；若天真地逐字串完整模擬，可能卡死在某個不停機的字串上。解法是交錯模擬（dovetailing）：

Soundness：\(\mathcal{S}\) 只在模擬中親眼看到 \(M\) 接受某字串 \(w_i\) 時才回答「接受」，此時 \(w_i \in L(M)\)，故 \(L(M) \ne \emptyset\)，\(\langle M\rangle \in E_{TM}\)。不誤報。

Completeness：若 \(\langle M\rangle \in E_{TM}\)，則存在某字串被接受；設它在枚舉中是第 \(i\) 個（\(w_i\)），且 \(M\) 在 \(n_i\) 步內接受它。取 \(k^{*} = \max(i, n_i)\)：在第 \(k^{*}\) 輪，\(\mathcal{S}\) 會把 \(w_i\) 模擬至少 \(n_i\) 步，必然看到接受並回答「接受」。不漏報。

\(\mathcal{S}\) 既 sound 又 complete，故 \(E_{TM}\) 是遞迴可枚舉的。\(\blacksquare\)

（注意 \(\mathcal{S}\) 不終止：當 \(L(M) = \emptyset\) 時它永遠繞圈——這與 (a) 的不可判定性一致。）

(c) \(\overline{E_{TM}}\) 不是遞迴可枚舉的（5 分）

反設 \(\overline{E_{TM}}\) 是遞迴可枚舉的。由 (b)，\(E_{TM}\) 也是遞迴可枚舉的；由上述定理，\(E_{TM}\) 便是可判定的——與 (a) 的結論矛盾。

\[\therefore\; \overline{E_{TM}} \text{ 不是遞迴可枚舉的。}\qquad\blacksquare\]

數學歸納法、DPLL 演算法、分治法 [25 分]

題目說明

(a) 歸納法證明 \(T(n) \ge \log_2 n\)（10 分）

欲證命題：\(P(n):\; T(n) \ge \log_2(n)\)，對所有 \(n \ge 1\)。

由於遞迴式把 \(n\) 送到 \(\lceil n/3\rceil\)（不是 \(n-1\)），採用強歸納法。

基底情況（\(n = 1\)）： \[T(1) = 1 \ge 0 = \log_2(1). \checkmark\]

歸納假設：設 \(n > 1\)，並假設對所有 \(1 \le m < n\) 皆有 \(T(m) \ge \log_2(m)\)。

歸納步驟：先確認遞迴引用的參數落在假設範圍內：對 \(n > 1\)， \[1 \le \left\lceil \frac{n}{3}\right\rceil \le \frac{n+2}{3} < n \qquad(\text{末一步因 } n + 2 < 3n \iff n > 1),\] 故可對 \(m = \lceil n/3\rceil\) 使用歸納假設。於是 \[\begin{align*} T(n) &= T\!\left(\left\lceil \frac{n}{3}\right\rceil\right) + 2 \;\ge\; \log_2\!\left(\left\lceil \frac{n}{3}\right\rceil\right) + 2 &&(\text{歸納假設})\\[2pt] &\ge\; \log_2\!\left(\frac{n}{3}\right) + 2 &&(\lceil n/3\rceil \ge n/3,\ \log_2 \text{ 遞增})\\[2pt] &=\; \log_2(n) - \log_2(3) + 2\\[2pt] &\ge\; \log_2(n) &&(\log_2 3 < \log_2 4 = 2). \end{align*}\] 即 \(P(n)\) 成立。

結論：由基底情況與歸納步驟，依強歸納法原理，\(T(n) \ge \log_2(n)\) 對所有 \(n \ge 1\) 成立。\(\blacksquare\)

(b) DPLL 演算法（10 分）

初始檢查。沒有單元子句。檢查純文字：\(P\)（正：4, 5；負：3, 6）混合；\(Q\)（正：1, 4, 6；負：2, 7）混合；\(S\)、\(T\) 皆混合；但 （僅在子句 (3)）。

步驟 1（純文字消去 \(R\)）：令 \(R = \text{True}\)，刪去子句 (3)。剩餘： \[(Q \lor \lnot S \lor \lnot T)_{(1)},\quad (\lnot Q \lor \lnot T)_{(2)},\quad (P \lor Q \lor S)_{(4)},\quad (P \lor \lnot S \lor T)_{(5)},\quad (\lnot P \lor Q)_{(6)},\quad (\lnot Q \lor T)_{(7)}.\] 仍無單元子句、無純文字。

步驟 2（分支：選 \(Q\)）。

分支一：\(Q = \text{True}\)。含 \(Q\) 的 (1)(4)(6) 被滿足刪除；(2)(7) 刪去 \(\lnot Q\)： \[(\lnot T)_{(2')},\qquad (P \lor \lnot S \lor T)_{(5)},\qquad (T)_{(7')}.\]

• 單元傳播 \((\lnot T)\)：令 \(T = \text{False}\)；子句 \((T)_{(7')}\) 刪去 \(T\) 後成為空子句 \(\square\)。

矛盾，分支一失敗。（本質原因：\((\lnot Q \lor \lnot T)\) 與 \((\lnot Q \lor T)\) 在 \(Q\) 為真時同時要求 \(\lnot T\) 與 \(T\)。）

分支二：\(Q = \text{False}\)。含 \(\lnot Q\) 的 (2)(7) 被滿足刪除；(1)(4)(6) 刪去 \(Q\)： \[(\lnot S \lor \lnot T)_{(1')},\qquad (P \lor S)_{(4')},\qquad (P \lor \lnot S \lor T)_{(5)},\qquad (\lnot P)_{(6')}.\]

• 單元傳播 \((\lnot P)\)：令 \(P = \text{False}\)；(4\('\)) 刪去 \(P\) 得 \((S)\)；(5) 刪去 \(P\) 得 \((\lnot S \lor T)\)。

• 單元傳播 \((S)\)：令 \(S = \text{True}\)；(1\('\)) 刪去 \(\lnot S\) 得 \((\lnot T)\)；\((\lnot S \lor T)\) 刪去 \(\lnot S\) 得 \((T)\)。

• 單元傳播 \((\lnot T)\)：令 \(T = \text{False}\)；子句 \((T)\) 成為空子句 \(\square\)。

矛盾，分支二失敗。

結論：變數 \(Q\) 的兩個分支都推導出空子句，DPLL 回傳 \[\textbf{Unsatisfiable（不可滿足）}.\] （快速驗證：(2) 與 (7) 強迫 \(Q\) 為假；(6) 再強迫 \(P\) 為假；(4) 強迫 \(S\) 為真；(5) 強迫 \(T\) 為真；但此時 (1) \(= Q \lor \lnot S \lor \lnot T\) 三個文字全假——的確無解。）

(c) 分治演算法範例：合併排序（Merge Sort）（5 分）

問題：給定長度 \(n\) 的數列 \(a_1, \dots, a_n\)，輸出由小到大排序後的數列。

演算法（分治三部曲）：

1. Divide（分割）：若 \(n \le 1\) 直接回傳（已排序）。否則把數列切成左半 \(a_1..a_{\lfloor n/2\rfloor}\) 與右半 \(a_{\lfloor n/2\rfloor+1}..a_n\)；

2. Conquer（征服）：對左、右兩半遞迴地呼叫合併排序，得到兩個已排序的子數列；

3. Combine（合併）：用兩根指標同時從兩個已排序子數列的開頭掃描，每次把較小的元素搬進輸出，直到兩邊都取完——線性時間 \(O(n)\) 完成合併。

正確性：對長度做歸納——長度 \(\le 1\) 顯然正確；假設遞迴呼叫正確排序兩半，合併步驟按大小交錯取出即得整體排序。

時間複雜度：遞迴關係為 \[T(n) = 2\,T(n/2) + O(n),\] \(a=2\), \(b=2\), \(c^{*} = \log_2 2 = 1\)，\(f(n) = O(n) = \Theta(n^{c^{*}})\)，Master 定理 Case 2 給出 \(T(n) = \Theta(n\log n)\)——優於插入排序等 \(\Theta(n^{2})\) 演算法。

HAMILTONIAN CYCLE：NP 成員資格與 SAT 歸約 [25 分]

題目說明

(a) HAMILTONIAN CYCLE \(\in\) NP（6 分）

非確定性多項式時間演算法：輸入 \(G = (V, E)\)，\(n = |V|\)。

1. 猜測（非確定性步驟）：非確定性地選出頂點的一個排列 \(\langle v_1, v_2, \dots, v_n\rangle\)；

2. 驗證（確定性步驟）：

   • 檢查 \(v_1, \dots, v_n\) 兩兩相異且涵蓋全部 \(V\)（即為一個排列）；

   • 對每個 \(i = 1, \dots, n-1\) 檢查 \(\{v_i, v_{i+1}\} \in E\)，並檢查 \(\{v_n, v_1\} \in E\)（收尾成迴路）；

3. 全部通過則接受，否則此分支拒絕。

時間分析：猜測需 \(O(n\log n)\) 個非確定性位元；驗證做 \(n\) 次相鄰性檢查與一次排列檢查，鄰接矩陣下共 \(O(n^{2})\)。多項式。

正確性：若 \(G\) 有 Hamiltonian cycle，存在某個猜測分支恰好列出該迴路的頂點順序並通過驗證；若沒有，所有分支都會在驗證中失敗。故此演算法在非確定性多項式時間內判定 HAMILTONIAN CYCLE，即它屬於 NP。\(\blacksquare\)

(b) 建構 \(G_F\)（9 分）

設 \(F\) 是 CNF 公式，變數為 \(x_1, \dots, x_n\)、子句為 \(c_1, \dots, c_k\)。標準建構（「菱形鏈」構造）：

（一）變數 gadget。為每個變數 \(x_i\) 建一個菱形（diamond）：頂節點 \(t_i\)、底節點 \(b_i\)，中間夾一條水平鏈 \(u_{i,1} \leftrightarrow u_{i,2} \leftrightarrow \cdots \leftrightarrow u_{i,m}\)（相鄰節點以雙向邊相連），並有邊 \(t_i \to u_{i,1}\)、\(t_i \to u_{i,m}\)、\(u_{i,1} \to b_i\)、\(u_{i,m} \to b_i\)。水平鏈可以由左往右或由右往左走——這兩種走法將分別對應 \(x_i = \text{True}\) 與 \(x_i = \text{False}\)。鏈上為每個子句 \(c_j\) 保留一對相鄰節點（各對之間以分隔節點隔開，故 \(m = O(k)\)）。

（二）子句節點。為每個子句 \(c_j\) 建一個單獨節點 \(c_j\)。若 \(x_i\) 以正文字出現在 \(c_j\)：加邊「左節點 \(\to c_j\)」與「\(c_j \to\) 右節點」（只有由左往右經過時能順路繞去 \(c_j\)）；若以負文字 \(\lnot x_i\) 出現：方向相反（只有由右往左時能繞去）。

（三）串接成環。\(b_i \to t_{i+1}\)（\(i = 1, \dots, n-1\)），並加 \(b_n \to t_1\) 使整體能閉合成迴路。

整體大小：節點 \(O(nk)\)、邊 \(O(nk)\)，建構顯然是輸入大小的多項式時間。取 \(G_F\) 為此圖，即得「\(F\) 可滿足 \(\iff\) \(G_F\) 有 Hamiltonian cycle」（由 (c)(d) 論證）。

(c) 可滿足 \(\Rightarrow\) 有 Hamiltonian cycle（5 分）

設 \(\sigma\) 是 \(F\) 的滿足指派。建構迴路如下：

1. 從 \(t_1\) 出發，依序走過每個菱形：若 \(\sigma(x_i) = \text{True}\)，把第 \(i\) 條水平鏈由左往右走完；若為 False 則由右往左；走完從 \(b_i\) 接到 \(t_{i+1}\)，最後由 \(b_n\) 回到 \(t_1\) 閉合。

2. 每個子句 \(c_j\) 因 \(\sigma\) 而含有至少一個為真的文字；挑選其中一個，設它來自變數 \(x_i\)。若是正文字，則 \(x_i\) 的鏈正被由左往右走，恰好能在 \(c_j\) 的保留節點對處「繞道」：左節點 \(\to c_j \to\) 右節點，再繼續前進；負文字則方向相反、同樣順路。每個子句節點恰繞道一次。

如此，所有菱形節點被主幹走過恰一次、每個子句節點被恰一次繞道拜訪，且首尾相接——這正是一條 Hamiltonian cycle。\(\blacksquare\)

(d) 有 Hamiltonian cycle \(\Rightarrow\) 可滿足（5 分）

設 \(H\) 是 \(G_F\) 的任一條 Hamiltonian cycle。

（一）迴路必呈「正規形」。由建構，進入菱形 \(i\) 只能經 \(t_i\)、離開只能經 \(b_i\)；且子句節點 \(c_j\) 的出入邊都連在同一對相鄰鏈節點上，若迴路從某菱形繞去 \(c_j\) 卻從別的菱形離開，就會使該對節點中的另一個再也無法被拜訪（其僅存的鄰居都已用過），與 Hamiltonian 矛盾。因此 \(H\) 必定：逐一走過每個菱形，並把每條水平鏈完整地由左往右或由右往左走完，繞道後立即回到同一條鏈的下一個節點。

（二）由方向讀出指派。定義 \(\sigma(x_i) = \text{True}\) 若 \(H\) 把第 \(i\) 條鏈由左往右走，否則 \(\sigma(x_i) = \text{False}\)。

（三）每個子句都被滿足。\(H\) 是 Hamiltonian，必定拜訪每個子句節點 \(c_j\)，而拜訪只能透過某個菱形 \(i\) 的繞道。繞道邊的方向設計使得：正文字的繞道只與「左往右」相容、負文字的繞道只與「右往左」相容。因此該繞道所在的文字在 \(\sigma\) 下為真，子句 \(c_j\) 被滿足。所有子句皆然，故 \(\sigma\) 滿足 \(F\)。\(\blacksquare\)