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_suit:,.,.:heart_suit:,.,
