NP-Completeness

內容目錄

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

    \[\phi = (\bar{x} \wedge y) \vee (x \wedge \bar{z})\]

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

    \[SAT = \{<\phi>| \phi \> is \> a \>satisfiable \> Boolean \> formula\}\]

定理:Cook-Levin Theorem

    \[SAT \in P \>\> iff \>\> P = NP\]

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

    \[\omega \in A \Leftrightarrow f(\omega) \in B\]

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

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

    \[A \leq_{p}B, B \leq_{p} C \Rightarrow A \leq_{p} C\]

至此所有的language屬於NP都可以在多項式時間內轉換到C
定義:
literal: 一個boolean variable或是一個negated boolean(variable x 或者 \bar{x})
clause: (x_{1} \vee \bar{v_{2}} \vee x_{3} \vee \bar{x_{4}})
conjunctive normal form (CNF):

    \[(x_{1} \vee x_{2} \vee \bar{x_{3}}) \wedge (x_{4} \vee \bar{x_{5}}) \wedge (x_{3} \vee \bar{x_{6}})\]

3CNF-formula:

    \[(x_{1} \vee x_{2} \vee \bar{x_{3}}) \wedge (x_{3} \vee \bar{x_{5}} \vee x_{6}) \wedge (x_{3} \vee \bar{x_{6}} \vee x_{4})\]

3SAT = \{<\phi>|\phi是一個satisfiable 3cnf-formula\}
定理:3SAT可以在多項式時間內轉換到CLIQUE
證明:讓\phi作為一個formula擁有k個clauses:

    \[\phi = (a_{1} \vee b_{1} \vee c_{1}) \wedge (a_{2} \vee b_{2} \vee c_{2}) \wedge … \wedge(a_{k} \vee b_{k} \vee c_{k}) \underset{\Longrightarrow}{f} <G, k>\]

    \[\phi = (x_{1} \vee x_{1} \vee x_{2}) \wedge (\bar{x_{1}} \vee \bar{x_{2}} \vee \bar{x_{2}}) \wedge (\bar{x_{1}} \vee x_{2} \vee x_{2})\]

其中f為多項式時間的轉換function
\phi要能夠滿足的話若且唯若\in CLIQUE

Cook-Levin Theorem

SAT \in NP-complete
證明:

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

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

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

f:多項式時間轉換問題A到SAT問題
輸入w作為問題A的instance,將w轉換產生成formula \phi
假設Q\Gamma作為N的state集合以及tape的alphabet
C = Q \cup \Gamma \cup {#}1 \leq i, j \leq n^{k}以及每一個s \in C,可以產生x_{i, j, s} \thicksim n^{2k}個variable
如果x_{i, j, s} = 1代表cell[i, j]包含s
設計一組\phi可以滿足variable與NTM N輸入w的結果產生一組accepting表

    \[\phi = \phi_{cell} \wedge \phi_{start} \wedge \phi_{move} \wedge \phi_{accept}\]

(1)

    \[\phi_{cell} = \underset{i \leq i, j \leq n^{k}}{\vee}[(\underset{s \in C}{\vee}x_{i,j,s}) \wedge (\underset{s, t \in C, s \neq t}{\wedge} (\bar{x_{i,j,s}} \vee \bar{x_{i,j,t}}))]\]

(2)

    \[\phi_{start} = x_{1,1,#} \wedge x_{1,2,q_{0}} \wedge x_{1,3,w_{1}} \wedge x_{1, 4,w_{2}} \wedge … \wedge x_{1,n+2,w_{n}} \wedge x_{1,n+3,\cup} \wedge … \wedge x_{x_{1},n^{k}-1, \cup} \wedge x_{1, n^{k}, #}\]

要確認的是第一個row是NTM N輸入w的start configuration,以上就完成表內的一行row,還要再另外產生n^{k}-1組row
(3)\phi_{accept}保證表內一定會產生一組accepting的configuration

    \[\phi_{accept} = \underset{1 \leq i, j \leq n^{k}}{\vee} x_{i,j,q_{accept}}\]

(4)\phi_{move}
保證表裡面的每一個row都可以合法地透過NTM N的transition rule來產生
\delta(q_{1},a) = {q_{1}, b, R}
\delta(q_{1},b) = {(q_{2}, c, L), (q_{2}, a, R)}
\delta(q_{2}, a) = {q_{2}, b, R}

合法範例

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

\phi_{move} = \underset{1 \leq i, j \leq n^{k}}{\vee}(i, j的表格內容必須是合法的) =

    \[\underset{a_{1},….,a_{6}}{\vee}(x_{i-1,j,a_{1}} \wedge x_{i,j,a_{2}} \wedge x_{i+1,j,a_{3}} \wedge x_{i-1, j+1, a_{4}} \wedge x_{i,j+1,a_{5}} \wedge x_{i+1,j+1,a_{6}})\]

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

\phi的大小是O(n^{2k}),讓|C| = l \thicksim 依據N設計的transition大小
總共所有variable會有O(n^{2k})
\phi_{cell}:O(n^{2k}), \phi_{start}:O(n^{k})
\phi_{accept}, \phi_{move}: O(n^{2k})因此轉換可以在多項式時間內完成

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

證明:3SAT屬於NP
SAT \leq_{p} 3SAT
(a_{1} \vee a_{2} \vee a_{3} \vee a_{4}) \equiv (a_{1} \vee a_{2} \vee z) \wedge (\bar{z} \vee a_{3} \vee a_{4})
如果l > 3, (a_{1} \vee a_{2} \vee a_{3} \vee …. \vee a_{l})

    \[\equiv (a_{1} \vee a_{2} \vee z_{1}) \wedge (\bar{z_{1}} \vee a_{3} \vee a_{2}) \wedge (\bar{z_{2}} \vee a_{4} \vee z_{3}) \wedge … \wedge (\bar{z_{l-3}} \vee a_{l-1} \vee a_{l})\]

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

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

\{2, 3\}是一組vertex cover
\{1, 3\}不是一組vertex cover
Vertex-Cover = {<G, k>|G是一個無向圖並且擁有k個點的vertex cover}
定理:Vertex-Cover屬於NP-complete
證明:Vertex-Cover屬於NP

    \[3SAT \leq_{p} VERTEX-COVER\]

    \[\phi = (x_{1} \vee x_{1} \vee x_{2}) \wedge (\bar{x_{1}} \vee \bar{x_{2}} \vee \bar{x_{2}}) \wedge (\bar{x_{1}} \vee x_{2} \vee x_{2})\]

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

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

SUBSET-SUM

SUBSET-SUM = {<S, t>|S = \{x_{1},…,x_{k}\}以及對於某些\{y_{1},…,y_{i}} \subseteq S, \sum_{y_{i}} = t}
定理:SUBSET-SUM屬於NP-complete
證明:SUBSET-SUM屬於NP

    \[3SAT \leq_{p} SUBSET-SUM\]

存在\phi是一個boolean formula擁有variables x_{1},…,x_{i}以及clauses c_{1},….,c_{k}

    \[\phi = c_{1} \wedge c_{2} \wedge …. \wedge c_{k}|\phi \rightarrow\ <S, t>\]

  1. 假設\phi滿足的話,建構一個子集合S,如果x_{i}給的值是TRUE,選擇y_{i},否則就另外選擇z_{i},對於每一次的i,一次只會選擇y_{i}z_{i}代表true或false,最後k個digits會把整個i加總起來算1,如果不到3的話由gh來補到3
  1. 假設一組S的子集合可以加總到t,可以建構一組滿足\phi的公式,如果這組子集合包含y_{i}我們就設定x_{i}為TRUE,否則設定x_{i}為FALSE,而這樣的條件可以滿足\phi
    整張表的大小是O((k+i)^{2}) \thicksim O(n^{2})

定理:HAMPATH \in NP-complete

    \[3SAT \leq_{p} HAMPATH\]

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

    \[\phi = (a_{1} \vee b_{1} \vee c_{1}) \wedge (a_{2} \vee b_{2} \vee c_{2}) \wedge … \wedge (a_{k} \vee b_{k} \vee c_{k})\]

每一個a,b,c可以看作literal的x_{i}或者\bar{x_{i}}以及x_{1},…..,x_{i}都是\phi的variables

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

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

定理:UHAMPATH屬於NP-complete

證明:

    \[HAMPATH \leq_{p} UHAMPATH\]

    \[Directed \> Graph \> G \rightarrow Undirected \> Graph \> G'\]

u \in V(G)
G'的點: u \Rightarrow u^{in}, u^{mid}, u^{out}
s \Rightarrow s^{out}, t \Rightarrow t^{in}
G'的邊: u \rightarrow v \in E(G) \Rightarrow u^{in} - u^{mid} - u^{out} - v^{in} - v^{mid} - v^{out}

如果s \rightarrow u_{1} \rightarrow u_{2} \rightarrow … \rightarrow u_{k} \rightarrow tG裡的Hamiltonian path
s^{out} - u^{in}_{1} - u^{mid}_{1} - u^{out}_{1} - u^{in}_{2} - u^{mid}_{2} - u^{out}_{2} - … - u^{in}_{k} - u^{mid}_{k} - u^{out}_{k} - t^{in}屬於G'裡的無向Hamiltonian path。

Scientia

我是Scientia,研究興趣包含Cryptology, Cryptographic Engineering, Security and Privacy, Computational Complexity, Quantum Cryptography, Cybersecurity, Anomaly Detection以及Hardware Security.

Related Posts

時間複雜度

通長在測量複雜度的時候會使用兩種分析方法:Worst-case analysisAverage-case analysis定義一個M是Deterministic Turing Machine並且會根據輸入決定停止規範M的執行時間或者時間複雜度可以表示成一個function…

不同的Turing Machine

讓Turing Machine擁有多組tape
\delta: Q \times \Gamma^{k} \rightarrow Q \times \Gamma^{k} \times {L, R}^{k}, k: tapes的數量…

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

You Missed

NP-Completeness

NP-Completeness

異常檢測 問題分類

異常檢測 問題分類

異常檢測 方法評估

異常檢測 方法評估

異常檢測簡介 Anomaly Detection

異常檢測簡介 Anomaly Detection

高斯消去法

高斯消去法

Vectors

Vectors