3 P、NP问题

3.1 P(polynomial time)问题

对于一个计算问题,将其输入编码成有穷的二进制串s。判定问题接收输入串s,并返回“yes”或者“no”。这个返回值记为A(s)。若存在多项式函数p,使得对每一个输入串s,算法A对s的计算至多在O(p(|s|))步终止,则称A有多项式运行时间。==P问题就是能在多项式时间内解决的问题==。P指Polynomia。

3.2 NP(nondeterministic polynomial time)问题

为了验证一个一个解,需要输入串s以及另外的“证书”串t。如果下述两条性质成立,则称B是问题X的有效验证程序:
(1)B是有两个输入变量s和t的多项式时间算法。
(2)存在多项式p使得对每一个输入串s,A(s)=yes当且仅当存在串t使得|t|≦p(|s|)且B(s,t)=yes。
==NP问题就是能在多项式时间验证答案正确与否的问题,即所有存在有效验证程序的问题的集合==。

3.3 P问题与NP问题的关系

定理5.P \subseteq NP.
即,所有的P问题都是NP问题。当一个问题是P问题时,我们可以在多项式时间内求出问题的解。若要验证一个解(记为t1)是否正确时,只需使用多项式时间求解出这个问题的解(记为t2),然后将t1和t2做比较即可验证答案是否正确。即,可以利用多项式时间验证答案正确与否。因此,P问题也是NP问题。可以看到,三元可满足性问题(3-SAT)、独立集问题、集合覆盖问题都是NP问题。
【讨论:P=NP?】
对于这个问题,还没有人利用一种有效的方法证明。目前计算机界普遍相信P≠NP。所以P问题是NP问题的真子集。

0
Posted in 算法设计与分析

Leave a Comment:

电子邮件地址不会被公开。