P、NP 和 NPC 问题：复杂度理论基础

在本章中，我们将探讨三类问题：P、NP 和 NPC，其中 NPC 代表 NP 完全问题。我们会先进行非正式的描述，并将在稍后给出更正式的定义。

类 P 包含那些可以在多项式时间内解决的问题。更准确地说，这类问题可以在时间 O(nk) 内解决，其中 k 是一个常数，n 是问题输入的大小。我们在之前的章节中研究的大多数问题都属于 P 类。

类 NP 包含那些可以在多项式时间内‘验证’的问题。什么是可验证的问题？如果我们获得了问题的‘证书’，我们可以通过对输入大小进行多项式时间复杂度的操作来验证证书是否正确。例如，在汉密尔顿回路问题中，给定一个有向图 G = (V, E)，证书将是一个包含 |V| 个顶点的序列 <v1, v2, v3, …, v|V|>。我们可以很容易地在多项式时间内检查 (vi, vi+1) ∈ E，其中 i = 1, 2, 3, …, |V|-1，并且 (v|V|, v1) ∈ E。再举一个例子，对于 3-CNF 可满足性问题，证书将是变量值的分配。我们可以通过多项式时间复杂度的操作来验证该分配是否满足布尔公式。

任何属于 P 类的問題也属于 NP 类，因为如果一个问题属于 P 类，则我们可以在不提供证书的情况下以多项式时间复杂度解决它。我们将在本章后面更正式地描述这一概念，但目前我们可以先相信 P ⊆ NP。目前尚未解决的问题是 P 是否为 NP 的一个真子集。