学习算法课学习到后期，都会进入一个看起来很理论话题：P、NP、NP-hard、NP-complete。这些概念想回答的核心问题是给各种问题和算法分类：
某个问题到底是“可以高效解决”，还是“很可能没有高效精确算法”？
这个判断非常重要。因为如果一个问题本质上是 NP-complete，那么你继续死磕“完美、快速、精确”的算法，可能方向就错了。更现实的做法往往是近似算法、启发式算法、剪枝搜索。
算法问题大致可以分成很多类型，其中复杂度理论特别喜欢研究一种问题：判定问题。
判定问题的答案只有两个：yes 或 no
例如：给定一个整数序列 \(S\)，问：是否存在两个元素相等？ 这就是一个判定问题。它只关心有没有重复元素，不要求你找出出现最多的元素，也不要求你统计所有频率。
再比如，给定一个图 \(G=(V,E)\) 和一个整数 \(k\)，问：图中是否存在一个大小至少为 \(k\) 的 clique？ 这也是判定问题。
（在无向图中，一个 clique，中文常译为“团”，指的是一组顶点，其中任意两个顶点之间都有边相连）
优化问题关心的是某个最优值，比如最大值或最小值。
例如：给定一个整数序列 \(S\)，问哪个元素出现频率最高？ 这是优化问题。
再比如，给定一个图 \(G\)，问：图中最大 clique 的大小是多少？ 这也是优化问题，叫做 MAX-CLIQUE。
再比如，给定一张带权图，问：从点 \(s\) 到点 \(t\) 的最短路径长度是多少？ 这是最短路径的优化版。
优化问题可以通过加入一个界限值 \(k\)，变成判定问题。
例如：
图中最大 clique 的大小是多少？
变成：图中是否存在大小至少为 \(k\) 的 clique？
从 \(s\) 到 \(t\) 的最短路径长度是多少？
变成：是否存在一条从 \(s\) 到 \(t\) 的路径，长度不超过 \(k\)？
经过所有城市并回到起点的最短路线是多少？
变成：是否存在一条经过所有城市并回到起点、总长度不超过 \(k\) 的路线？
这件事很重要，因为复杂度理论经常优先研究判定问题。如果优化问题容易，那么对应的判定问题也容易。比如你已经能快速求出最短路径长度 \(d\)，那么要回答“是否存在长度不超过 \(k\) 的路径”，只需要判断：\( d \le k \)。
因此，对很多自然优化问题来说，如果我们能快速求出最优值，就能快速回答对应的判定问题。反过来，如果某个判定版已经被证明很难，那么对应的优化版通常也不会更容易，很多时候可以进一步证明为 NP-hard。
P 是一类判定问题。它的定义是：可以用确定性算法在多项式时间内解决的判定问题，属于 P。
确定性算法就是每一步都只有一个确定选择的算法。同样的输入，每次运行，执行路径一样，输出也一样。
大部分我们平时写的算法都是确定性算法，比如：二分查找、快速排序、BFS、DFS、Dijkstra、动态规划
当然，快速排序如果随机选 pivot，那它可以是随机算法。但如果 pivot 选择规则固定，它就是确定性的。
如果输入规模是 \(n\)，算法运行时间可以表示为：
\[O(n^k) \]
其中 \(k\) 是某个常数，那么这个算法就是多项式时间算法。比如 \(O(n)\)、\(O(n \log n)\)、\(O(n^2)\) 和 \(O(n^3)\)。
在复杂度理论里，通常把多项式时间视为“高效可解”的理论边界。为什么呢？
主要原因：\(O(n)\)、\(O(n^2)\)、\(O(n^3)\) 虽然内部差别很大，但总体上比指数增长温和得多。相比之下，\(O(2^n)\)、\(O(3^n)\) 或者 \(O(n!)\) 增长极快，当 \(n=100\) 时，\(2^{100}\) 已经是天文数字。
其次，如果 A 可以多项式时间规约到 B，而 B 可以多项式时间解决，那么 A 也可以多项式时间解决。
因为：
\[poly(n) + poly(n) = poly(n) \]
并且：
\[poly(poly(n)) = poly(n) \]
多项式的复合仍是多项式。这使得整个 NP-complete 理论非常稳定。
当然，多项式时间不等于现实中一定快。例如 \(O(n^{100})\) 虽然是多项式，但几乎没有实际意义，实际应用可能不如指数算法。但在复杂度理论里，还是使用多项式时间来刻画问题的结构性难度。
2-COLORING
给定一个无向图，问：能不能用两种颜色给图中的顶点染色，使得任意相邻顶点颜色不同？
这个问题等价于判断图是否是二分图，可以用 BFS 或 DFS 在线性时间内解决。
SHORTEST PATH 的判定版
给定一张带权图、两个点 \(s,t\) 和一个数 \(k\)，问：是否存在一条从 \(s\) 到 \(t\) 的路径，长度不超过 \(k\)？
如果边权非负，可以先用 Dijkstra 求出最短路径 \(d\)，然后判断 \(d \le k\)。
当然，我们已经知道，即使是 SHORTEST PATH 的优化版，也可以在多项式时间轻松解决。
2-SAT
SAT，全称 satisfiability，中文常译为“可满足性问题”。它问的是：
给定一个布尔公式，是否存在一种变量赋值，使整个公式为真？
例如：
\[(x \lor y) \land (\neg x \lor z) \]
这个公式里有变量 \(x,y,z\)。如果存在一组 true/false 赋值让整个公式为 true，那么它就是可满足的。
2-SAT 是 SAT 的一个限制版本：每个子句里至多有 2 个 literal（比如上面的例子）。可以证明 2-SAT 可以在多项式时间内解决，所以它属于 P。
NP 也是一类判定问题。它的核心思想不是“能不能快速求出答案”，而是：如果有一个候选解，能否在多项式时间内验证它的对错？
更正式地说，一个判定问题属于 NP，如果对于所有 yes 实例，都存在一个多项式长度的证据，并且这个证据可以在多项式时间内被验证。
CLIQUE 问题是：给定一个图 \(G=(V,E)\) 和整数 \(k\)，问图中是否存在大小至少为 \(k\) 的 clique？
这个问题属于 NP。虽然要设计一个多项式算法来求解很困难，但 NP 问题的定义只需要我能验证解的对错就可以。如果有人告诉你：
这 \(k\) 个点就是一个 clique。
你只需要检查这些点是否两两相连。检查 \( \frac{k(k-1)}{2} \) 次，这是多项式时间。
总结：NP 问题答案可能难找，但答案一旦给出，容易检查。
数独更符合我们对这个问题的理解。给你一个空白很多的数独盘面，求解答案可能需要搜索很多可能性和大量运算。但如果有人给你一个填好的数独，你检查它是否合法很容易了。所以这类问题最有 NP 的味道。当然，常见的 \(9\times 9\) 数独规模太小，不适合直接讨论渐近复杂度。复杂度理论里通常讨论的是推广到更大规模的数独变体。不过作为直觉例子，数独很好地体现了 NP 的味道：答案可能难找，但答案一旦给出，容易检查。
前面已经提过，如果一个问题能多项式时间直接求解，那么当然也能多项式时间验证。所以：\( P \subseteq NP \)，真正不知道的是：\( P = NP? \)
理解 NP-hard 和 NP-complete 之前，必须先理解规约。
规约的意思是：
把问题 A 的实例，在多项式时间内转换成问题 B 的实例，并且保持 yes/no 答案一致。
记作：
\[A \le_{poly} B \]
意思是：A 可以多项式时间规约到 B。
也就是说，如果我们有一个能解决 B 的算法，那么就可以这样解决 A：
所以：如果 \(A \le_{poly} B\)，那么 B 至少和 A 一样难。A 可以借助 B 来解决，所以 B 的能力至少覆盖 A。
在无向图中，independent set，中文常译为“独立集”，指的是一组顶点，其中任意两个顶点之间都没有边。
CLIQUE 刚好相反：
现在有一个问题：给定图 \(G\) 和整数 \(k\)，问 \(G\) 中是否存在大小为 \(k\) 的 independent set？
我们可以把它规约到 CLIQUE。做法是构造 \(G\) 的补图 \(\overline{G}\)。补图的意思是：原来有边的地方，补图里没有边、原来没有边的地方，补图里有边
于是：
\[G \text{ 中有大小为 } k \text{ 的 independent set} \]
当且仅当：
\[\overline{G} \text{ 中有大小为 } k \text{ 的 clique} \]
所以：
\[INDEPENDENT\ SET \le_{poly} CLIQUE \]
这个转换显然可以在多项式时间内完成。
在无向图中，vertex cover，中文常译为“顶点覆盖”，指的是一组顶点，使得图中每条边至少有一个端点被选中。
VERTEX COVER 的判定版是：
给定图 \(G\) 和整数 \(k\)，问 \(G\) 中是否存在大小至少为 \(k\) 的 independent set？
CLIQUE 可以规约到 VERTEX COVER。
核心关系是：
\[G \text{ 有大小为 } k \text{ 的 clique} \]
当且仅当：
\[\overline{G} \text{ 有大小为 } n-k \text{ 的 vertex cover} \]
因为 \(G\) 中的 clique 等价于 \(\overline{G}\) 中的 independent set，一个 independent set 的补集就是 vertex cover。所以给定 CLIQUE 实例 \((G,k)\)，我们可以转换成 VERTEX COVER 实例：
\[(\overline{G}, n-k) \]
如果 VERTEX COVER 的答案是 yes，那么原 CLIQUE 的答案也是 yes。
刚刚介绍了 2-SAT。3-SAT 是 SAT 的一个限制版本：公式是合取范式，每个子句 clause 中包含 3 个文字 literal。一个 literal 可以是变量本身，比如 \(x\)，也可以是变量的否定，比如 \(\neg x\)。
例如：
\[(x \lor y \lor z) \land (\neg x \lor y \lor w) \land (x \lor \neg z \lor w) \]
有些教材把 3-SAT 定义为每个子句“恰好 3 个 literal”，有些教材定义为“至多 3 个 literal”。这两个版本都可以证明为 NP-complete，差别不影响本文。
3-SAT 可以规约到 CLIQUE。构造思路是：
为什么这样有效？
一个大小为 \(m\) 的 clique，意味着我们可以从每个 clause 中选出一个 literal，并且这些 literal 两两不矛盾。这就对应着一组可以让公式为真的赋值。
所以：
\[\text{3SAT} \le_{\operatorname{poly}} \text{CLIQUE} \]
这个例子非常经典。
一个问题 \(\Pi\) 是 NP-hard，如果：NP 中的所有问题都可以多项式时间规约到 \(\Pi\)。
也就是说，对于任意 \(\Pi' \in NP\)，都有：
\[\Pi' \le_{poly} \Pi \]
直观理解：NP-hard 问题至少和 NP 里最难的问题一样难。
不过 NP-hard 不要求这个问题本身属于 NP。因此 NP-hard 问题可以是：
MAX-CLIQUE 是优化问题：给定图 \(G\)，输出图中最大 clique 的大小。
如果你能快速解决 MAX-CLIQUE，那么你就能快速解决 CLIQUE 的判定版：图 \(G\) 中是否存在大小至少为 \(k\) 的 clique？
所以，MAX-CLIQUE 至少和 CLIQUE 一样难。而 CLIQUE 是 NP-complete，因此 MAX-CLIQUE 是 NP-hard。
旅行商问题 TSP 的优化版：给定若干城市以及城市之间的距离，求一条经过每个城市一次并回到起点的最短路线。
如果优化版 TSP 能快速解决，那么判定版 TSP 也能快速解决。所以优化版 TSP 是 NP-hard。
停机问题是：给定一个程序和输入，问这个程序运行后是否会停机？
这和前面的问题区别更大了，是一个不可判定问题。不存在一个算法能够对所有程序和输入都给出正确 yes/no 答案。
停机问题可以是 NP-hard，但它不是 NP-complete，因为 NP-complete 要求问题属于 NP，而停机问题连 NP 都不是。
这个例子说明 NP-hard 的范围比 NP-complete 大得多。
NP-complete，中文叫 NP 完全。它既可以被多项式时间验证，又至少和 NP 中最难的问题一样难。关系可以写成：
\[NP\text{-complete} = NP \cap NP\text{-hard} \]
SAT 是：给定一个布尔公式，是否存在一种变量赋值，使公式为真？它属于 NP。
因为如果有人给出一组变量赋值，我们可以把它代入公式，然后在多项式时间内检查公式是否为 true。
SAT 也是 NP-hard 和 NP-complete。Cook-Levin 定理证明了：任何 NP 问题都可以多项式时间规约到 SAT。
SAT 的重要性在于：它是第一个被证明为 NP-complete 的问题。从 SAT 出发，人们又证明了大量问题是 NP-complete。
3-SAT 是 NP-complete。3-SAT 是 SAT 的特殊版本，每个 clause 只有 3 个 literal。它仍然是 NP-complete。3-SAT 是很多 NP-complete 证明的起点。
常见证明链条包括：
\[3SAT \le_{poly} CLIQUE \]
\[3SAT \le_{poly} 3COLORING \]
\[3SAT \le_{poly} HAMILTONIAN\ PATH \]
CLIQUE 是 NP-complete：它属于 NP，因为给定一组点，可以快速检查它们是否两两相连。它是 NP-hard，因为可以从 3-SAT 规约过来。
VERTEX COVER 是 NP-complete：
给定图 \(G\) 和整数 \(k\)，问是否存在不超过 \(k\) 个顶点，覆盖图中的所有边？
它属于 NP，因为给定一个点集，可以快速检查每条边是否至少有一个端点在点集中。它是 NP-hard，因为 CLIQUE 可以规约到 VERTEX COVER。
3-COLORING 是 NP-complete：
给定一个无向图，问能否用 3 种颜色给所有顶点染色，使得任意相邻顶点颜色不同？
它属于 NP，因为给定一种染色方案，可以快速检查所有边两端颜色是否不同。它也是 NP-hard，可以通过 3-SAT 规约证明。
这里有一个很有意思的对比：
颜色数只从 2 增加到 3，问题难度发生了巨大变化。
证明一个问题 \(\Pi\) 是 NP-complete，通常有一个标准模板。
首先要证明：
\[\Pi \in NP \]
也就是：如果有一个候选解，你可以在多项式时间内验证它。
然后找一个已经知道是 NP-complete 的问题 \(\Pi'\)，证明：
\[\Pi' \le_{poly} \Pi \]
意思是：已知难问题 \(\Pi'\) 可以多项式时间转换成当前问题 \(\Pi\)。
这一步说明：
如果 \(\Pi\) 容易，那么 \(\Pi'\) 也容易。
但 \(\Pi'\) 已经是 NP-complete，所以 \(\Pi\) 至少也同样难。
结合两步骤，就得到：\( \Pi \text{ 是 NP-complete} \)
一定要注意规约方向。要证明当前问题 \(\Pi\) 很难，应该证明：
\[\text{已知难问题} \le_{\operatorname{poly}} \Pi \]
而不是证明：
\[\Pi \le_{\operatorname{poly}} \text{已知难问题} \]
后者只能说明当前问题不比已知难问题更难，不能证明当前问题也很难。
很多 NP-complete 证明会形成一条链：
\[SAT \le_{poly} 3SAT \le_{poly} CLIQUE \le_{poly} VERTEX\ COVER \]
也可以有：
\[3SAT \le_{poly} 3COLORING \]
\[3SAT \le_{poly} HAMILTONIAN\ PATH \]
\[SUBSET\ SUM \le_{poly} KNAPSACK \]
规约具有传递性。如果：\( A \le_{poly} B \)，并且：\( B \le_{poly} C \)，那么：\( A \le_{poly} C \)。只要有几个“源头问题”被证明很难，后面就可以不断扩展出一整张 NP-complete 问题网络。
区分这些概念的意义不只是给问题贴标签，而是帮助我们判断应该投入什么样的算法努力。
如果一个问题属于 P，我们通常会继续寻找更快、更省空间、更适合工程实现的精确算法。
如果一个问题是 NP-complete，那么它很可能不存在多项式时间精确算法。此时更现实的方向包括：
如果一个问题是 NP-hard 但不一定属于 NP，比如某些优化问题，那么它至少和 NP-complete 问题一样难。我们不能指望一般情况下总能快速求出精确最优解。
所以，这些分类的作用是帮助我们避免把时间浪费在错误目标上：不是所有问题都适合追求“又快、又精确、又通用”的算法。
还有一个很容易被忽略的点：输入中的数字是如何编码的。
比如最短路径问题中，边权是整数还是浮点数，通常不会改变它属于 P 这个事实。算法主要受顶点数和边数影响。在理论分析中，我们通常假定比较边权大小、相加边权这些基本操作可以在合理时间内完成。
但有些问题就不一样，比如 0-1 背包问题。
0-1 背包问题是：
给定若干物品，每个物品有重量和价值，在容量限制内最大化总价值。
经典动态规划的复杂度是：
\[O(nW) \]
其中 \(n\) 是物品数量，\(W\) 是背包容量。
如果 \(W\) 很小，这个算法很好用。但如果 \(W\) 是一个非常大的数字，算法就会很慢。
关键在于：输入里写下数字 \(W\)，需要的长度大约是 \(\log W\)，而不是 \(W\) 本身。例如，用二进制写下一个很大的容量，只需要几十位或几百位，但动态规划却可能要跑和 \(W\) 成正比的步数。
因此，\(O(nW)\) 不是关于输入长度的多项式时间，而是关于数值大小的多项式时间。这种复杂度叫做伪多项式时间。
这解释了为什么有些问题的“数值大小”非常重要。背包问题属于典型的弱 NP-hard 问题：当数值范围较小时，可以用伪多项式 DP；当数值范围很大时，困难就会暴露出来。
最后，我们回到最著名的问题：
所有可以快速验证的问题，是否也都可以快速求解？
显然 \( P \subseteq NP \)，因为能快速求解，一定能快速验证。
但是 \( P = NP \) 吗？反过来是否成立，没人知道。
如果：
\[P = NP \]
那意味着所有 NP 问题，包括 SAT、CLIQUE、3-COLORING、TSP 判定版等，都有多项式时间算法。这会对优化、密码学、自动证明、程序分析、AI 规划等领域产生巨大影响。
如果：
\[P \ne NP \]
那就说明确实存在一些问题：答案可以快速验证，但不能快速求出。这符合大多数人的直觉，也是当前更广泛相信的方向。
但到目前为止，没人证明 \(P=NP\)，也没人证明 \(P \ne NP\)。
在 P vs NP 尚未解决之前，NP-complete 为我们提供了一种判断问题困难性的强有力证据。当你证明一个问题是 NP-complete，你实际上是在说：如果这个问题有多项式时间算法，那么所有 NP 问题都有多项式时间算法。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。