P问题与NP问题的关系

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