有一种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)