P、NP和NP完全问题：简要概述

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

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

'NP'类包括那些可以在多项式时间内'验证'的问题。什么是'验证'问题？如果我们以某种方式获得了解决方案的'证书'，那么我们可以在多项式时间内验证该证书是否正确。例如，在哈密顿回路问题中，给定一个有向图G=(V,E)，证书将是一个包含|V|个顶点的序列<v1,v2,v3,…,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'的真子集。