P、NP和NP完全问题：计算机科学中的关键概念

在本章中，我们将提到三类问题：P、NP和NPC，后者是NP完全问题。我们在此非正式地描述它们，稍后我们将更正式地定义它们。

类P包括那些可以在多项式时间内解决的问题。更具体地说，它们是可以在O(nk)时间内解决的问题，其中k是某个常数，n是问题输入的大小。大多数在前几章中研究的问题都在P中。

类NP包括那些可以在多项式时间内'验证'的问题。什么是可验证的问题？如果我们某种方式获得了一个解决方案的'证书'，那么我们可以在多项式时间内验证证书是否正确。例如，在哈密顿循环问题中，给定一个有向图G=(V，E)，一个证书将是一个序列<v1，v2，v3，…，v|v|>，其中|V|个顶点。我们可以很容易地检查在多项式时间内，对于i=1、2、3、… …、|V|-1，都有(vi，vi+1)∈E，以及(v|v|，v1)∈E。另一个例子是对于3-CNF可满足性，证书将是变量的值分配。我们可以在多项式时间内检查此分配是否满足布尔公式。

任何P中的问题也属于NP，因为如果问题在P中，那么我们甚至不需要提供证书就可以在多项式时间内解决它。我们将在本章后面更正式地表述这个概念，但现在我们可以相信P⊆NP。开放性问题是P是否是NP的真子集。