计算与判定：P、NP、NP-hard 和 NP-complete 问题

这篇文章介绍了计算与判定：P、NP、NP-hard 和 NP-complete 问题，分享给大家做个参考，收藏极客资料网收获更多编程知识

学习算法课学习到后期，都会进入一个看起来很理论话题：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 是一类判定问题。它的定义是：可以用确定性算法在多项式时间内解决的判定问题，属于 P。

确定性算法

确定性算法就是每一步都只有一个确定选择的算法。同样的输入，每次运行，执行路径一样，输出也一样。

大部分我们平时写的算法都是确定性算法，比如：二分查找、快速排序、BFS、DFS、Dijkstra、动态规划

当然，快速排序如果随机选 pivot，那它可以是随机算法。但如果 pivot 选择规则固定，它就是确定性的。

多项式时间

如果输入规模是 \(n\)，算法运行时间可以表示为：

其中 \(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 也可以多项式时间解决。

因为：

并且：

多项式的复合仍是多项式。这使得整个 NP-complete 理论非常稳定。

当然，多项式时间不等于现实中一定快。例如 \(O(n^{100})\) 虽然是多项式，但几乎没有实际意义，实际应用可能不如指数算法。但在复杂度理论里，还是使用多项式时间来刻画问题的结构性难度。

典型的 P 问题例子

2-COLORING

给定一个无向图，问：能不能用两种颜色给图中的顶点染色，使得任意相邻顶点颜色不同？

这个问题等价于判断图是否是二分图，可以用 BFS 或 DFS 在线性时间内解决。

SHORTEST PATH 的判定版

给定一张带权图、两个点 \(s,t\) 和一个数 \(k\)，问：是否存在一条从 \(s\) 到 \(t\) 的路径，长度不超过 \(k\)？

如果边权非负，可以先用 Dijkstra 求出最短路径 \(d\)，然后判断 \(d \le k\)。

当然，我们已经知道，即使是 SHORTEST PATH 的优化版，也可以在多项式时间轻松解决。

2-SAT

SAT，全称 satisfiability，中文常译为“可满足性问题”。它问的是：

给定一个布尔公式，是否存在一种变量赋值，使整个公式为真？

例如：

这个公式里有变量 \(x,y,z\)。如果存在一组 true/false 赋值让整个公式为 true，那么它就是可满足的。

2-SAT 是 SAT 的一个限制版本：每个子句里至多有 2 个 literal（比如上面的例子）。可以证明 2-SAT 可以在多项式时间内解决，所以它属于 P。

NP：可以高效验证的问题

NP 也是一类判定问题。它的核心思想不是“能不能快速求出答案”，而是：如果有一个候选解，能否在多项式时间内验证它的对错？

更正式地说，一个判定问题属于 NP，如果对于所有 yes 实例，都存在一个多项式长度的证据，并且这个证据可以在多项式时间内被验证。

用 CLIQUE 理解 NP

CLIQUE 问题是：给定一个图 \(G=(V,E)\) 和整数 \(k\)，问图中是否存在大小至少为 \(k\) 的 clique？

这个问题属于 NP。虽然要设计一个多项式算法来求解很困难，但 NP 问题的定义只需要我能验证解的对错就可以。如果有人告诉你：

这 \(k\) 个点就是一个 clique。

你只需要检查这些点是否两两相连。检查 \( \frac{k(k-1)}{2} \) 次，这是多项式时间。

总结：NP 问题答案可能难找，但答案一旦给出，容易检查。

用数独理解 NP

数独更符合我们对这个问题的理解。给你一个空白很多的数独盘面，求解答案可能需要搜索很多可能性和大量运算。但如果有人给你一个填好的数独，你检查它是否合法很容易了。所以这类问题最有 NP 的味道。当然，常见的 \(9\times 9\) 数独规模太小，不适合直接讨论渐近复杂度。复杂度理论里通常讨论的是推广到更大规模的数独变体。不过作为直觉例子，数独很好地体现了 NP 的味道：答案可能难找，但答案一旦给出，容易检查。

所有 P 问题都属于 NP

前面已经提过，如果一个问题能多项式时间直接求解，那么当然也能多项式时间验证。所以：\( P \subseteq NP \)，真正不知道的是：\( P = NP? \)

规约：把一个问题翻译成另一个问题

理解 NP-hard 和 NP-complete 之前，必须先理解规约。

规约的意思是：

把问题 A 的实例，在多项式时间内转换成问题 B 的实例，并且保持 yes/no 答案一致。

记作：

意思是：A 可以多项式时间规约到 B。

也就是说，如果我们有一个能解决 B 的算法，那么就可以这样解决 A：

1. 把 A 的输入转换成 B 的输入
2. 调用 B 的算法
3. 返回 B 的答案

所以：如果 \(A \le_{poly} B\)，那么 B 至少和 A 一样难。A 可以借助 B 来解决，所以 B 的能力至少覆盖 A。

例子：INDEPENDENT SET 规约到 CLIQUE

在无向图中，independent set，中文常译为“独立集”，指的是一组顶点，其中任意两个顶点之间都没有边。

CLIQUE 刚好相反：

• clique 要求任意两个点之间都有边
• independent set 要求任意两个点之间都没有边

现在有一个问题：给定图 \(G\) 和整数 \(k\)，问 \(G\) 中是否存在大小为 \(k\) 的 independent set？

我们可以把它规约到 CLIQUE。做法是构造 \(G\) 的补图 \(\overline{G}\)。补图的意思是：原来有边的地方，补图里没有边、原来没有边的地方，补图里有边

于是：

当且仅当：

所以：

这个转换显然可以在多项式时间内完成。

例子：CLIQUE 规约到 VERTEX COVER

在无向图中，vertex cover，中文常译为“顶点覆盖”，指的是一组顶点，使得图中每条边至少有一个端点被选中。

VERTEX COVER 的判定版是：

给定图 \(G\) 和整数 \(k\)，问 \(G\) 中是否存在大小至少为 \(k\) 的 independent set？

CLIQUE 可以规约到 VERTEX COVER。

核心关系是：

当且仅当：

因为 \(G\) 中的 clique 等价于 \(\overline{G}\) 中的 independent set，一个 independent set 的补集就是 vertex cover。所以给定 CLIQUE 实例 \((G,k)\)，我们可以转换成 VERTEX COVER 实例：

如果 VERTEX COVER 的答案是 yes，那么原 CLIQUE 的答案也是 yes。

例子：3-SAT 规约到 CLIQUE

刚刚介绍了 2-SAT。3-SAT 是 SAT 的一个限制版本：公式是合取范式，每个子句 clause 中包含 3 个文字 literal。一个 literal 可以是变量本身，比如 \(x\)，也可以是变量的否定，比如 \(\neg x\)。

例如：

有些教材把 3-SAT 定义为每个子句“恰好 3 个 literal”，有些教材定义为“至多 3 个 literal”。这两个版本都可以证明为 NP-complete，差别不影响本文。

3-SAT 可以规约到 CLIQUE。构造思路是：

• 每个 clause 里的每个 literal 建一个点；
• 不同 clause 的两个 literal 如果不冲突，就连边；
• 冲突的意思是一个是 \(x\)，另一个是 \(\neg x\)；
• 如果公式有 \(m\) 个 clause，就问图中是否存在大小至少为 \(m\) 的 clique。

为什么这样有效？

一个大小为 \(m\) 的 clique，意味着我们可以从每个 clause 中选出一个 literal，并且这些 literal 两两不矛盾。这就对应着一组可以让公式为真的赋值。

所以：

这个例子非常经典。

NP-hard：至少和 NP 中最难的问题一样难

一个问题 \(\Pi\) 是 NP-hard，如果：NP 中的所有问题都可以多项式时间规约到 \(\Pi\)。

也就是说，对于任意 \(\Pi' \in NP\)，都有：

直观理解：NP-hard 问题至少和 NP 里最难的问题一样难。

不过 NP-hard 不要求这个问题本身属于 NP。因此 NP-hard 问题可以是：

• 判定问题
• 优化问题
• 甚至不是可判定问题

例子：MAX-CLIQUE

MAX-CLIQUE 是优化问题：给定图 \(G\)，输出图中最大 clique 的大小。

如果你能快速解决 MAX-CLIQUE，那么你就能快速解决 CLIQUE 的判定版：图 \(G\) 中是否存在大小至少为 \(k\) 的 clique？

所以，MAX-CLIQUE 至少和 CLIQUE 一样难。而 CLIQUE 是 NP-complete，因此 MAX-CLIQUE 是 NP-hard。

例子：TSP 优化版是 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-complete，中文叫 NP 完全。它既可以被多项式时间验证，又至少和 NP 中最难的问题一样难。关系可以写成：

经典问题：SAT 是 NP-complete

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 证明的起点。

常见证明链条包括：

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-COLORING 属于 P
• 3-COLORING 是 NP-complete

颜色数只从 2 增加到 3，问题难度发生了巨大变化。

如何证明一个问题是 NP-complete

证明一个问题 \(\Pi\) 是 NP-complete，通常有一个标准模板。

证明它属于 NP

首先要证明：

也就是：如果有一个候选解，你可以在多项式时间内验证它。

找一个已知 NP-complete 问题规约到它

然后找一个已经知道是 NP-complete 的问题 \(\Pi'\)，证明：

意思是：已知难问题 \(\Pi'\) 可以多项式时间转换成当前问题 \(\Pi\)。

这一步说明：

如果 \(\Pi\) 容易，那么 \(\Pi'\) 也容易。

但 \(\Pi'\) 已经是 NP-complete，所以 \(\Pi\) 至少也同样难。

结合两步骤，就得到：\( \Pi \text{ 是 NP-complete} \)

一定要注意规约方向。要证明当前问题 \(\Pi\) 很难，应该证明：

而不是证明：

后者只能说明当前问题不比已知难问题更难，不能证明当前问题也很难。

常见的证明路线

很多 NP-complete 证明会形成一条链：

也可以有：

规约具有传递性。如果：\( A \le_{poly} B \)，并且：\( B \le_{poly} C \)，那么：\( A \le_{poly} C \)。只要有几个“源头问题”被证明很难，后面就可以不断扩展出一整张 NP-complete 问题网络。

为什么要区分 P、NP、NP-hard、NP-complete

区分这些概念的意义不只是给问题贴标签，而是帮助我们判断应该投入什么样的算法努力。

如果一个问题属于 P，我们通常会继续寻找更快、更省空间、更适合工程实现的精确算法。

如果一个问题是 NP-complete，那么它很可能不存在多项式时间精确算法。此时更现实的方向包括：

• 近似算法：不求最优，但保证离最优解不太远；
• 启发式算法：不保证理论最优，但在实际数据上效果好；
• 随机算法：通过随机化获得更好的平均表现；
• 剪枝搜索：仍然搜索，但尽量减少不必要的分支；
• 参数化算法：当某些参数很小时，问题可以高效求解；
• 利用特殊结构：实际输入可能不是最坏情况。

如果一个问题是 NP-hard 但不一定属于 NP，比如某些优化问题，那么它至少和 NP-complete 问题一样难。我们不能指望一般情况下总能快速求出精确最优解。

所以，这些分类的作用是帮助我们避免把时间浪费在错误目标上：不是所有问题都适合追求“又快、又精确、又通用”的算法。

进阶补充：伪多项式时间

还有一个很容易被忽略的点：输入中的数字是如何编码的。

比如最短路径问题中，边权是整数还是浮点数，通常不会改变它属于 P 这个事实。算法主要受顶点数和边数影响。在理论分析中，我们通常假定比较边权大小、相加边权这些基本操作可以在合理时间内完成。

但有些问题就不一样，比如 0-1 背包问题。

0-1 背包问题是：

给定若干物品，每个物品有重量和价值，在容量限制内最大化总价值。

经典动态规划的复杂度是：

其中 \(n\) 是物品数量，\(W\) 是背包容量。

如果 \(W\) 很小，这个算法很好用。但如果 \(W\) 是一个非常大的数字，算法就会很慢。

关键在于：输入里写下数字 \(W\)，需要的长度大约是 \(\log W\)，而不是 \(W\) 本身。例如，用二进制写下一个很大的容量，只需要几十位或几百位，但动态规划却可能要跑和 \(W\) 成正比的步数。

因此，\(O(nW)\) 不是关于输入长度的多项式时间，而是关于数值大小的多项式时间。这种复杂度叫做伪多项式时间。

这解释了为什么有些问题的“数值大小”非常重要。背包问题属于典型的弱 NP-hard 问题：当数值范围较小时，可以用伪多项式 DP；当数值范围很大时，困难就会暴露出来。

P vs NP 世纪难题

最后，我们回到最著名的问题：

所有可以快速验证的问题，是否也都可以快速求解？

显然 \( P \subseteq NP \)，因为能快速求解，一定能快速验证。

但是 \( P = NP \) 吗？反过来是否成立，没人知道。

如果：

那意味着所有 NP 问题，包括 SAT、CLIQUE、3-COLORING、TSP 判定版等，都有多项式时间算法。这会对优化、密码学、自动证明、程序分析、AI 规划等领域产生巨大影响。

如果：

那就说明确实存在一些问题：答案可以快速验证，但不能快速求出。这符合大多数人的直觉，也是当前更广泛相信的方向。

但到目前为止，没人证明 \(P=NP\)，也没人证明 \(P \ne NP\)。

在 P vs NP 尚未解决之前，NP-complete 为我们提供了一种判断问题困难性的强有力证据。当你证明一个问题是 NP-complete，你实际上是在说：如果这个问题有多项式时间算法，那么所有 NP 问题都有多项式时间算法。

文章来源:https://www.cnblogs.com/ofnoname/p/19938344
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！