2015年6月14日 星期日

Formal Language - Ch16 NP完全 NP-Complete, NPC

於 沒有留言:
標籤：
 

NP完全 NP-Complete, NPC
NP完全是計算複雜度理論中，決定性問題的等級之一。NPC 問題，是NP (非決定性多項式時間) 中最難的決定性問題。

一個決定性問題C若是為NPC，則代表它對NP是完備的，這表示：
  • 它是一個NP問題，且
  • 其他屬於NP的問題都可歸約成它。

這個定義是史提芬·古克所提出。雖然NPC這個詞並沒有出現在這篇論文上任何地方。在這個資訊科學會議上，資訊科學家激動地討論NPC問題是否可以在一個確定型圖靈機上以多項式時間求解。John Hopcroft總結與會眾人的共識，認為由於沒有人能對某一命題提出駁倒對方的證明，此問題不會於現在解決。此命題就是知名的。
P和NP相等嗎?。
尚未有人能提出證明，說明NPC問題是否能在多項式時間中解決，使得此問題成為著名的數學中未解決的問題。 


[傳送門] Cook-Levin理論與卡普的二十一個NP-完全問題
這部分的科學史還滿有趣的~ 更多八卦和秘辛在此~
http://mropengate.blogspot.tw/2015/06/algorithm-cook-levinnp.html


[例題1] if $P = NP$, NP is closed under complement
P is closed under complementation so if $P = NP$, then NP is closed under complementation as well.

that is, if NP is not closed under complement then $P \neq NP$
$x \in NP \rightarrow x \in P \rightarrow \bar{x} \in P \rightarrow \bar{x} \in NP \rightarrow x \in co-NP$


[例題2] If PATH is not NPC, $P \neq NP$
PATH 本身是P問題，因此：
if $P = NP$, then PATH is NPC.  $\rightarrow$  if PATH is not NPC, then $P \neq NP$.




Cook-Levin theorem預備知識 - 布爾可滿足性問題
布爾可滿足性問題的成員(instance)是一個布爾表達式，也就是一些布爾變數跟布爾邏輯運算符的組合。如果說一個表達式是可滿足的(satisfiable)，則存在某些給予布爾變數真值的方式，可以使這個表達式的值為真。


合取範式 Conjunctive normal form, CNF
在布爾邏輯中，如果它是子句的合取，則稱一個公式是合取範式(CNF)，也就是將一堆由「$\vee$」形成的「句子」「$\wedge$」在一起，則稱該公式的型式為CNF。

例如，下列所有公式都是 CNF:
$A \wedge B$
$\neg A \wedge (B \vee C)$
$(A \vee B) \wedge (\neg B \vee C \vee \neg D) \wedge (D \vee \neg E)$
$(\neg B \vee C)$
而下列不是:
$\neg (B \vee C)$
$(A \wedge B) \vee C$
$A \wedge (B \vee (D \wedge E))$
上述三個公式分別等價於合取範式的下列三個公式:
$\neg B \wedge \neg C$
$(A \vee C) \wedge (B \vee C)$
$A \wedge (B \vee D) \wedge (B \vee E)$

關於CNF重要的事實 :
  • 所有命題公式都可以轉換成 CNF 的等價公式 (利用邏輯等價的規則 : 雙重否定律、迪摩根定律和分配律。)
  • 某些情況下，CNF 的轉換可能導致公式的子句數量指數性爆漲。
    例如 : 把下述 非-CNF 公式轉換成 CNF 生成有 $2^n$ 個子句的公式
    $(X_1 \wedge Y_1) \vee (X_2 \wedge Y_2) \vee \dots \vee (X_n \wedge Y_n)$

CNF相關英文名詞解釋 :
  • Literal : $x$ or $x'$
  • Clause: $(x_1 \vee x_2' \vee x_3' \vee x_4)$
  • Conjunctive normal form, cnf-formula:
    $(x_1 \vee x_2' \vee x_3' \vee x_4) \wedge (x_3 \vee x_5' \vee x_6) \wedge (x_3 \vee x_6')$




Cook-Levin理論
Cook-Levin理論一個非常重要的結果是，如果存在一個決定型多項式時間演算法，可以解決布爾可滿足性問題(SAT)的話，則對於所有的NP裡面的問題都存在決定型多項式時間演算法，而證出P = NP，也就是理論電腦科學裡著名的P/NP問題。

以下是一些關於Cook-Levin理論的結論：
  1. 如果NP-complete問題屬於P，那P = NP
  2. 如果B可多項式歸約為C且B是NPComplete，那C也是NP-Complete。



布爾可滿足性問題(SAT)是NP完全問題
Cook–Levin理論證明了布爾可滿足性問題(SAT)是NP完全問題。換句話說，任何NP裡面的問題可以在多項式時間內，使用圖靈機，將之歸約成「一個布林方程式是否存在解」這個問題。

( 證明有點複雜，暫時無法完整參透，故附上原文，歡迎大家交流交流^^ )

3-布爾可滿足性問題(3-SAT)是NP完全問題
化成「完全相同」結果的表達式所需之複雜度：
$ Boolean  \rightarrow_{多項式時間}  CNF  \rightarrow_{非多項式時間}  3CNF $
但 CNF歸約成 3CNF不需要相等，只要可以mapping :
$w \in A \leftrightarrow f(w) \in B$

mapping的方法：
  • 若 $(X_1 ∨ X_2)$ 化成 $( X_1 ∨ X_1 ∨ X_2)$，只有兩個Literal，多重複一個。
  • 若 $(X_1∨X_2∨X_3∨X_4)$ 則化成 $(X_1∨X_2∨ X_5 ) ∧ ( X_5' ∨X_3∨X_4)$
  • 若 $(X_1∨X_2∨X_3∨X_4∨X_5)$ 則化成 $(X_1∨X_2∨X_6)∧(X_6'∨X_3∨X_7) ∧(X_7'∨X_4∨X_5)$，以此類推。




NP-完全問題舉例

問題頂點覆蓋問題 Vertex Cover Problem
$VERTEX_{COVER} = \{<G, k>\ |\ G 是一個有 k 頂點覆蓋的無向圖\}$
頂點覆蓋 (vertex cover)：這個圖中的每一個邊都連到一群選定的節點
證明概念：3SAT 歸約成 VERTEX-COVER

 mapping的方法：
  • 上面排每個literal的正跟負，下面排每個clause出現的literal。
  • 把上下一樣literal的連起來。

 例題：


團問題 Clique Problem
$CLIQUE = \{<G,k>\ |\ G 是一個具有k團(k-clique)的無向圖\}$
團 (clique)：一個圖中兩兩相鄰的一個點集，或稱為一個完全子圖(complete subgraph)
證明概念：3SAT 歸約成 Clique

mapping的方法：
  • 把每個clause的literal寫成如下一組一組的形式。
  • 對每個點，(a)同clause不連，(b) 正跟反不連 (因為正跟反不同組不影響結果)

例題：


漢米頓路徑問題 Hamiltonian Path Problem
$HAMPATH = \{(G, s, t)\ |\ G 是一個有從s到t，具有漢米頓路徑的有向圖 \}$
漢米頓路徑 (hamiltonian path)：每一點剛好經過一次的路線，起點和終點不相同。可能有許多種，也可能不存在。
證明概念：3SAT 歸約成 HAM-PATH，一個「菱形」的節點數為 3k+5 (k 是 clause 數量)。

mapping的方法：

  • 一個菱形結構對應一個variable，菱形結構中的節點數量取決於clause數量 (n = 3k + 3)
  • 右側放置代表clause的節點
  • 配對variable和clause，正的literal順向相連，付的literal逆向相連，如圖。




例題：


子集合加總問題 Subset Sum Problem
$SUBSET_{SUM} = \{<S, t>\ |\ S = \{ x_1, ... , x_k \}，$ 
$拿 \{ y_1, ... , y_l \} 包含於 \{ x_1, ... , x_k \} , 有 y 總和=t \}$ 
子集合加總 (Subset Sum)：從給定的一堆整數中挑一些整數加起來，看是不是目標數。
證明概念：3SAT 歸約成SUBSET-SUM

mapping的方法：

例題：

  • $S = \{t_1,f_1,t_2,f_2,t_3,f_3,x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4\}$
  • $T = 1113333 (3 variable + 4 clause)、X_i = t_i、X_i' = f_i$
  • $t_i , f_i$ 代表$X_i$用或不用 、 $t_j , f_j$ 代表這個符號出現在哪些clause
  • $x_j ,y_j$ 是想辦法把答案 $j$ 行湊成3


[例題] LPATH is NPC
Let LPATH denote the language:
LPATH = {<G, s, t, k> | G contains a simple path of length at least k from s to t}.

Ans:

 a. LPATH is in NP
LPATH is in NP because a certificate for <G, s, t, k> simply consists of the
sequence of edges in a simple path from s to t with length at least k, so that for this kind of certificate, we can find a corresponding polynomial time DTM verifier.


b. NP problem can be reduced LPATH in polynomial time
To further show that every NP problem can be reduced LPATH in polynomial time,
we shall reduce HAMPATH to LPATH. Consider the following TM F that computes a
reduction f from HAMPATH to LPATH :
F = "On input <G, s, t>, Output <G, s, t, n − 1>, where n is the number of vertices in G."
Firstly, if there is a hamiltonian path from s to t in G, the path would have length n − 1
so that <G, s, t, n − 1> is in LPATH. On the other hand, if <G, s, t, n − 1> is in LPATH, the simple path from s to t has length n − 1, so that it must be hamiltonian. Thus,
$<G, s, t> \in HAMPATH \leftrightarrow <G, s, t, n − 1> \in LPATH$
Also, it is obvious that the above reduction runs in polynomial time. This implies HAMPATH is polynomial-time reducible to LPATH. Thus, LPATH is NP-complete.




[站長小結語] 正規語言筆記完結
作為正規語言筆記的結束，真有一點點莫名的感慨..(果然是讀到壞掉了)，最後以一個複雜度的統整圖作為結束，希望大家喜歡這個系列的文章：）





References

Wiki - NP完全

Wiki - P/NP問題

交大陳穎平教授正規語言講義






沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)
技術提供：Blogger.
 
© 2024 Mr. Opengate