NP-Completeness

內容目錄

• Cook-Levin Theorem
  • 合法範例
  • 推論(Cor)：3SAT是NP-complete
  • 推論(Cor)：CLIQUE屬於NP-complete
  • SUBSET-SUM
  • 定理：$HAMPATH \in NP-complete$
  • 定理：UHAMPATH屬於NP-complete

首先需要一個問題叫做布林公式(Boolean formula)會像：

裡面的每一個符號稱作variable，每一個variable可以給0或1的值就像在做布林運算，一個boolean formula要滿足的話要讓各個variable做完計算後輸出1
而有一種問題叫做satisfiability problem就是倚靠boolean formula是否滿足來達成條件

定理：Cook-Levin Theorem

定義：
如果存在多項式時間的Turing Machine M可以接受任何輸入w，並且在tape裡步驟之後停止並且輸出結果就稱這是一個多項式時間可運算的function
定義：
如果存在一個多項式時間可計算的function ，能輸入任何字串，代表可以讓language A在多項式時間內映射(mapping)轉換(reducible)到language B上，可以表示成或者可以表示成以下的對應函數：

這個function 做的事情是讓問題A在多項式時間內轉換到問題B
定義：如果 並且 , 則代表
證明：
存在一組多項式時間Turing Machine M可以決定B的結果並且作為多項式時間轉換將A問題換成B問題
N = 輸入任何字串

1. 計算
2. 放進輸入執行M並且不管M有沒有輸出都一定要輸出一個結果(這樣才符合algorithm的定義)
   定義：
   如果一個language B滿足以下兩個條件就可以稱作NP-complete
   (1) 問題B屬於NP
   (2) 任何問題A屬於NP並且在多項式時間轉換到問題B
   (如果只有條件(2)滿足的話叫做NP-hard的特性)
   定理：如果B是NP-complete並且，那麼
   證明：參照多項式時間轉換的定義
   定義：如果B是NP-complete並且對於，那麼C也會是NP-complete
   證明：存在任何的language 能夠在多項式時間內轉換到
   是NP-complete, 任何的language 都可以在多項式時間內轉換到B

至此所有的language屬於NP都可以在多項式時間內轉換到C
定義：
literal: 一個boolean variable或是一個negated boolean(variable 或者 )
clause:
conjunctive normal form (CNF):

3CNF-formula:

3SAT = 是一個satisfiable 3cnf-formula
定理：3SAT可以在多項式時間內轉換到CLIQUE
證明：讓作為一個formula擁有個clauses:

其中為多項式時間的轉換function
而要能夠滿足的話若且唯若

Cook-Levin Theorem

證明：

1. 
   • 一個NTM可以猜formula的variable並且在驗證過後看是否滿足
2. 對於任何的並且A可以在多項式時間內轉換到SAT問題上
   • 假設N是一個Non-deterministic Turing Machine可以在時間內決定A的輸出，，NTM N存在一組表輸入w制定出大小的表，每一列是NTM的每一條分支在計算輸入w的configuration，如果任何一列結果是accepting的configuration就代表整個表輸出就是accepting

任何accepting的表都是跟NTM N輸入w字串計算後的分支有關

NTM N能夠accept輸入w就代表存在accepting表能決定輸出結果是accept或是reject

多項式時間轉換問題A到SAT問題
輸入w作為問題A的instance，將w轉換產生成formula
假設跟作為N的state集合以及tape的alphabet
讓 從以及每一個，可以產生個variable
如果代表cell[i, j]包含
設計一組可以滿足variable與NTM N輸入w的結果產生一組accepting表

(1)

(2)

要確認的是第一個row是NTM N輸入w的start configuration，以上就完成表內的一行row，還要再另外產生組row
(3)保證表內一定會產生一組accepting的configuration

(4)：
保證表裡面的每一個row都可以合法地透過NTM N的transition rule來產生

合法範例

Claim: 首先檢查第一層的row是不是start configuration，如果是的話代表接下來表內的內容都是合法的，並且上一層跟下一層的configuration都要遵照transition rule

(的表格內容必須是合法的) =

需要一次看六格是不是合法的

的大小是，讓 依據N設計的transition大小
總共所有variable會有

因此轉換可以在多項式時間內完成

推論(Cor)：3SAT是NP-complete

證明：3SAT屬於NP


如果

推論(Cor)：CLIQUE屬於NP-complete

圖G的頂點覆蓋(Vertex cover of G)：如果G屬於一個無向圖，G裡覆蓋的頂點(Vertex cover)是圖G裡一個子集合能夠讓G的每一條邊都接著一個點

是一組vertex cover
不是一組vertex cover
Vertex-Cover = {|G是一個無向圖並且擁有k個點的vertex cover}
定理：Vertex-Cover屬於NP-complete
證明：Vertex-Cover屬於NP

靠以上的轉換方法來證明滿足的話代表G確實存在k個node的vertex cover
讓擁有個variable以及個clauses使得

1. 另外設計gadgets作為輔助的元件，一個true variable來自每個variable gadgets，兩個node來自clause gadget
2. 每三個邊可以連接variable gadgets跟clause gadget來覆蓋

SUBSET-SUM

SUBSET-SUM = {以及對於某些}
定理：SUBSET-SUM屬於NP-complete
證明：SUBSET-SUM屬於NP

存在是一個boolean formula擁有variables 以及clauses

1. 假設滿足的話，建構一個子集合，如果給的值是TRUE，選擇，否則就另外選擇，對於每一次的i，一次只會選擇或代表true或false，最後k個digits會把整個加總起來算1，如果不到3的話由跟來補到3

2. 假設一組S的子集合可以加總到，可以建構一組滿足的公式，如果這組子集合包含我們就設定為TRUE，否則設定為FALSE，而這樣的條件可以滿足
   整張表的大小是

定理：

證明：存在一組3cnf-formula擁有k個clauses

每一個可以看作literal的或者以及都是的variables

如果存在一組可以滿足的參數，選擇clause裡面其中一個literal給TRUE
如果存在可以得到true的結果，代表存在一組Hamiltonian path從走到
如果Hamiltonian path是，意思是可以從上面的鑽石型路徑頂端node走到最尾端的node，代表可以輕鬆找到一組滿足3CNF的路徑，因為每一組clause的點出現在路徑裡，只要點存在並且給TRUE的值，就可以接著走下去，如果是走路徑就讓每一個node放TRUE，反之走每一個點給False。
而Hamiltonian path必須是的

假設有兩種case:
case 1: 是一個離群的點
case 2: 是一個離群的點
在兩種情況下，路徑不包含的點
在case 1: 路徑沒辦法從或者進入，因為路徑走到了其他的點上
在case 2: 路徑沒辦法從進入，因為跟一樣是獨立的node在此種情況

定理：UHAMPATH屬於NP-complete

證明：

的點:

的邊:

如果是裡的Hamiltonian path
則 屬於裡的無向Hamiltonian path。