有一種Yes/No類型的問題 Q ( Q is a decision version problem in NP )
可找到一多項式時間演算法 A ( there exists a polynomial time algorithm A )
當在 X是Q的Yes instance時, X伴隨有一項資料Y(X), 可供A驗證
( For a Yes instance X of Q, there exists a certificate Y(X) such that A(Y)=1 )
Cook's Thm 證明了:
去解這類問題 等效於去解化成長串的一 Boolean function( F(X)=1, Does X exist? ).
==) Boolean Function Satisfiability is NP-Complete.
==) 誰能解SAT in polynomial time 就能解所有 NP 問題 in polynomial time.
Reduction:
另有研究說 SAT可以在polynomial time內 轉成其他的NP問題來解 像TSP, Clique,...
==) 如果TSP, Clique 有polynomial time的解法 那SAT也有 那所有NP問題都有
==) TSP, Clique 也是NP-Complete的成員
難度: NP = PCP(log(n),1) , 還有比NP 更大的類 PSPACE, EXP, NEXP
一般相信NP-complete的問題 還沒有polynomail time 的解法( 用Turing Machine執行)
舉例: ( Integers ) Set Partition
X是2n個正整數 Q問是否可以 分成sum,個數 都一樣的兩堆 ?
如果有人答Yes 那他就要負舉證責任 必需提供分法(certificate Y)與驗證法(A)
讓我們可以很快地(polynomial time內)驗證
可是若我們想自己找答案 可能要檢查極多的部分集合 C(2n,n)/2 ==> 指數時間
==) 很像分隊鬥牛可用到 :)
※ 引述《cockybastard (沒朋友)》之銘言：
: 請問如果要對非本科系的人解釋NP-Complete的意思和概念
: 要如何解釋比較易懂
: 另外就是有沒有比較適當的例子可以幫助此概念的理解
: 謝謝
※ 編輯: zhim 來自: 140.115.51.64 (06/04 01:36)