Proof. 確定性圖靈機是非確定性圖靈機的特例(\(\delta\)的每個值都是單元素集合),故多項式時間的 DTM 本身就是多項式時間的 NDTM。 ◻

證明(改寫演算法). 四個步驟,反覆套用直到形式正確:

步驟 1)改寫所有蘊含: \[(F\to G)\ \rightsquigarrow\ (\neg F\vee G).\]

步驟 2)用 De Morgan 律把否定推進括號內,直到只貼著變數: \[\neg(F\wedge G)\ \rightsquigarrow\ (\neg F\vee\neg G), \qquad \neg(F\vee G)\ \rightsquigarrow\ (\neg F\wedge\neg G).\]

步驟 3)用消去律刪除雙重否定: \[\neg\neg F\ \rightsquigarrow\ F.\]

步驟 4)用分配律整理形狀:

• 求 DNF:把析取「浮出表面」 \[F\wedge(G\vee H)\ \rightsquigarrow\ (F\wedge G)\vee(F\wedge H), \qquad (G\vee H)\wedge F\ \rightsquigarrow\ (G\wedge F)\vee(H\wedge F);\]

• 求 CNF:把合取「浮出表面」 \[F\vee(G\wedge H)\ \rightsquigarrow\ (F\vee G)\wedge(F\vee H), \qquad (G\wedge H)\vee F\ \rightsquigarrow\ (G\vee F)\wedge(H\vee F).\]

每步都保持邏輯等價,且程序必定終止。 ◻

Proof. 輸入)給定 CNF 公式\(F\)(設有\(n\)個變數)。

步驟 1)確定性的做法:計算整張真值表即可判定可滿足性。但真值表有\(2^n\)列——不是多項式!

步驟 2)然而,非確定性機器可以平行地評估每一列:NDTM 先非確定性地「猜」一組真值指派(每個變數分支成 True/False 兩條),然後在自己那條分支上評估\(F\)。評估一列只需檢查至多\(n\)個布林運算子——多項式!

只要\(F\)可滿足,就存在一條分支猜中滿足指派並接受;反之所有分支都拒絕。故\(\textsc{Sat}\in\textbf{NP}\)。 ◻

Proof. 步驟 1)假設 (i) \(Y\)是 NP-hard,(ii) \(Y\le_pX\)。

步驟 2)由 (i),對所有\(Z\in\textbf{NP}\)有\(Z\le_pY\)。

步驟 3)由 (ii) 與傳遞性(引理 19a): \[Z\le_pY\le_pX\quad\text{對所有 }Z\in\textbf{NP},\] 故\(X\)是 NP-hard。 ◻

證明. 上界已證(定理 15)。下界(每個 NP 問題\(\le_p\textsc{Sat}\))的想法:把任意多項式時間 NDTM 的計算表「編碼成布林公式」——詳細證明見下一週。Q.E.D.(soon) ◻

Proof. 輸入)無向圖\(G=(V,E)\)(\(n=|V|\))與整數\(k>2\)。

步驟 1)確定性的做法:逐一檢查每個大小\(k\)的頂點子集。但子集共有\(\binom{n}{k}\)個——不是多項式!

步驟 2)然而,非確定性機器可以平行地檢查每個子集:每條分支猜一個大小\(k\)的子集,然後只需檢查\(\binom{k}{2}\le k^2\)條邊是否都存在——多項式! ◻

Proof. 輸入)給定 CNF 公式\(F\),設其有\(k\)個子句。

步驟 1)目標:構造圖\(G_F=(V,E)\)並選整數\(k\),使得 \[F\text{ 可滿足}\iff G_F\text{ 含有大小 }k\text{ 的 clique}.\]

步驟 2)頂點:子句\(i\)中每個文字\(L\),都建立一個頂點\(L^i\)(同一文字出現在不同子句要分開計)。邊: \[(L_1^i,\ L_2^j)\in E \iff i\ne j\ \text{且}\ L_1\not\equiv\neg L_2 .\] 即:不同子句的兩個文字之間連邊,除非它們互相矛盾(\(P\)對\(\neg P\))。同一子句內部一律不連邊。

步驟 3)取\(k=F\)的子句數。

步驟 4)驗證兩個方向:

• (\(\Rightarrow\))若\(F\)可滿足,取一組滿足指派;每個子句至少有一個為真的文字,各挑一個,得到\(k\)個頂點。它們來自不同子句,且同時為真的文字不可能互相矛盾,故兩兩相鄰——大小\(k\)的 clique。

• (\(\Leftarrow\))若\(G_F\)有大小\(k\)的 clique:同一子句內無邊,故\(k\)個頂點必然每個子句恰一個;又 clique 中無矛盾對,故「讓這些文字全為真」是一致的指派(其餘變數任意),它滿足每個子句——\(F\)可滿足。

構造顯然可在多項式時間完成,故\(\textsc{Sat}\le_p\textsc{Clique}\)。 ◻

Proof. 上界:定理 25(\(\textsc{Clique}\in\textbf{NP}\))。下界:Sat 是 NP-hard(Cook–Levin)且\(\textsc{Sat}\le_p\textsc{Clique}\)(定理 26),由定理 21,Clique 是 NP-hard。 ◻

Proof. 輸入)無向圖\(G=(V,E)\),\(n=|V|\)。

步驟 1)確定性的做法:逐一檢查頂點的每種排列是否構成迴圈。但排列共有\(n!\)種——不是多項式!

步驟 2)然而,NDTM 可以平行地檢查每個排列:每條分支猜一個排列,然後只需檢查\(n\)條邊(相鄰頂點是否相連、首尾是否相連)——多項式! ◻

證明(構造概要). 輸入)給定 CNF 公式\(F\)(變數\(x_1,\dots,x_n\),子句\(C_1,\dots,C_k\))。

步驟 1)目標:構造圖\(G_F\)使得 \[F\text{ 可滿足}\iff G_F\text{ 有 Hamiltonian 迴圈}.\]

步驟 2)變數 gadget:每個變數\(x_i\)配一個「菱形」結構——上下兩個端點,中間夾一條水平節點列(相鄰節點間有雙向邊):

步驟 3)關鍵觀察:Hamiltonian 路徑要吃掉整條水平列,通過這個 gadget 只有兩種走法: \[\underbrace{\text{由左到右}}_{\text{解讀為 }x_i=\text{True}} \qquad\text{或}\qquad \underbrace{\text{由右到左}}_{\text{解讀為 }x_i=\text{False}}\]

步驟 4)把\(n\)個菱形上下串接成一個大環(上一個的出口接下一個的入口,最後一個接回第一個)。此時圖恰有\(2^n\)條 Hamiltonian 迴圈,與\(2^n\)組真值指派一一對應。

接著為每個子句\(C_j\)增設一個子句節點:在水平列上為每個子句保留一對相鄰節點;若文字\(x_i\)出現在\(C_j\),就從\(x_i\)那列的第\(j\)對節點,沿「左到右」方向接出一條到\(C_j\)再接回來的繞道(detour);若出現的是\(\neg x_i\),則沿「右到左」方向接繞道。

以\(F=(P\vee\neg Q)\wedge(\neg P\vee\neg R)\)為例的整體結構(示意;繞道以虛線表示):

步驟 5)驗證兩個方向:

• (\(\Rightarrow\))若\(F\)有滿足指派:每個變數依其真值決定該列方向;每個子句\(C_j\)至少有一個文字為真,挑其中一個,其所在列的行進方向恰好「順向」,可順路繞經\(C_j\)一次再回來。所有節點(含子句節點)恰被經過一次——Hamiltonian 迴圈。

• (\(\Leftarrow\))若\(G_F\)有 Hamiltonian 迴圈:可證迴圈必須「規規矩矩」地逐個菱形走(進入子句節點後必須立刻回到同一列的相鄰位置,否則必有節點無法被覆蓋)。於是每列有明確方向,讀出指派:左到右\(=\text{True}\)、右到左\(=\text{False}\)。迴圈造訪了每個\(C_j\),表示每個子句至少有一個文字順向——即至少一個文字為真,\(F\)被滿足。

整個構造的大小是\(O(nk)\),可在多項式時間完成,故\(\textsc{Sat}\le_p\textsc{Hamiltonian}\)。 ◻

Proof. 上界:定理 30。下界:\(\textsc{Sat}\le_p\textsc{Hamiltonian}\)(定理 31)加上定理 21。 ◻