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

这个判断非常重要。因为如果一个问题本质上是 NP-complete那么你继续死磕“完美、快速、精确”的算法可能方向就错了。更现实的做法往往是近似算法、启发式算法、剪枝搜索。判定问题和优化问题算法问题大致可以分成很多类型其中复杂度理论特别喜欢研究一种问题判定问题。判定问题判定问题的答案只有两个yes 或 no例如给定一个整数序列 SS问是否存在两个元素相等这就是一个判定问题。它只关心有没有重复元素不要求你找出出现最多的元素也不要求你统计所有频率。再比如给定一个图 G(V,E)G(V,E) 和一个整数 kk问图中是否存在一个大小至少为 kk 的 clique这也是判定问题。在无向图中一个 clique中文常译为“团”指的是一组顶点其中任意两个顶点之间都有边相连优化问题优化问题关心的是某个最优值比如最大值或最小值。例如给定一个整数序列 SS问哪个元素出现频率最高这是优化问题。再比如给定一个图 GG问图中最大 clique 的大小是多少这也是优化问题叫做MAX-CLIQUE。再比如给定一张带权图问从点 ss 到点 tt 的最短路径长度是多少这是最短路径的优化版。优化问题如何变成判定问题优化问题可以通过加入一个界限值 kk变成判定问题。例如图中最大 clique 的大小是多少变成图中是否存在大小至少为 kk 的 clique从 ss 到 tt 的最短路径长度是多少变成是否存在一条从 ss 到 tt 的路径长度不超过 kk经过所有城市并回到起点的最短路线是多少变成是否存在一条经过所有城市并回到起点、总长度不超过 kk 的路线这件事很重要因为复杂度理论经常优先研究判定问题。如果优化问题容易那么对应的判定问题也容易。比如你已经能快速求出最短路径长度 dd那么要回答“是否存在长度不超过 kk 的路径”只需要判断d≤kd≤k。因此对很多自然优化问题来说如果我们能快速求出最优值就能快速回答对应的判定问题。反过来如果某个判定版已经被证明很难那么对应的优化版通常也不会更容易很多时候可以进一步证明为 NP-hard。P可以高效解决的问题P 是一类判定问题。它的定义是可以用确定性算法在多项式时间内解决的判定问题属于 P。确定性算法确定性算法就是每一步都只有一个确定选择的算法。同样的输入每次运行执行路径一样输出也一样。大部分我们平时写的算法都是确定性算法比如二分查找、快速排序、BFS、DFS、Dijkstra、动态规划当然快速排序如果随机选 pivot那它可以是随机算法。但如果 pivot 选择规则固定它就是确定性的。多项式时间如果输入规模是 nn算法运行时间可以表示为O(nk)O(nk)其中 kk 是某个常数那么这个算法就是多项式时间算法。比如 O(n)O(n)、O(nlog⁡n)O(nlogn)、O(n2)O(n2) 和 O(n3)O(n3)。在复杂度理论里通常把多项式时间视为“高效可解”的理论边界。为什么呢主要原因O(n)O(n)、O(n2)O(n2)、O(n3)O(n3) 虽然内部差别很大但总体上比指数增长温和得多。相比之下O(2n)O(2n)、O(3n)O(3n) 或者 O(n!)O(n!) 增长极快当 n100n100 时21002100 已经是天文数字。其次如果 A 可以多项式时间规约到 B而 B 可以多项式时间解决那么 A 也可以多项式时间解决。因为poly(n)poly(n)poly(n)poly(n)poly(n)poly(n)并且poly(poly(n))poly(n)poly(poly(n))poly(n)多项式的复合仍是多项式。这使得整个 NP-complete 理论非常稳定。当然多项式时间不等于现实中一定快。例如 O(n100)O(n100) 虽然是多项式但几乎没有实际意义实际应用可能不如指数算法。但在复杂度理论里还是使用多项式时间来刻画问题的结构性难度。典型的 P 问题例子2-COLORING给定一个无向图问能不能用两种颜色给图中的顶点染色使得任意相邻顶点颜色不同这个问题等价于判断图是否是二分图可以用 BFS 或 DFS 在线性时间内解决。SHORTEST PATH 的判定版给定一张带权图、两个点 s,ts,t 和一个数 kk问是否存在一条从 ss 到 tt 的路径长度不超过 kk如果边权非负可以先用 Dijkstra 求出最短路径 dd然后判断 d≤kd≤k。当然我们已经知道即使是 SHORTEST PATH 的优化版也可以在多项式时间轻松解决。2-SATSAT全称 satisfiability中文常译为“可满足性问题”。它问的是给定一个布尔公式是否存在一种变量赋值使整个公式为真例如(x∨y)∧(¬x∨z)(x∨y)∧(¬x∨z)这个公式里有变量 x,y,zx,y,z。如果存在一组 true/false 赋值让整个公式为 true那么它就是可满足的。2-SAT 是 SAT 的一个限制版本每个子句里至多有 2 个 literal比如上面的例子。可以证明 2-SAT 可以在多项式时间内解决所以它属于 P。NP可以高效验证的问题NP 也是一类判定问题。它的核心思想不是“能不能快速求出答案”而是如果有一个候选解能否在多项式时间内验证它的对错更正式地说一个判定问题属于 NP如果对于所有 yes 实例都存在一个多项式长度的证据并且这个证据可以在多项式时间内被验证。用 CLIQUE 理解 NPCLIQUE 问题是给定一个图 G(V,E)G(V,E) 和整数 kk问图中是否存在大小至少为 kk 的 clique这个问题属于 NP。虽然要设计一个多项式算法来求解很困难但 NP 问题的定义只需要我能验证解的对错就可以。如果有人告诉你这 kk 个点就是一个 clique。你只需要检查这些点是否两两相连。检查 k(k−1)22k(k−1)​ 次这是多项式时间。总结NP 问题答案可能难找但答案一旦给出容易检查。用数独理解 NP数独更符合我们对这个问题的理解。给你一个空白很多的数独盘面求解答案可能需要搜索很多可能性和大量运算。但如果有人给你一个填好的数独你检查它是否合法很容易了。所以这类问题最有 NP 的味道。当然常见的 9×99×9 数独规模太小不适合直接讨论渐近复杂度。复杂度理论里通常讨论的是推广到更大规模的数独变体。不过作为直觉例子数独很好地体现了 NP 的味道答案可能难找但答案一旦给出容易检查。所有 P 问题都属于 NP。前面已经提过如果一个问题能多项式时间直接求解那么当然也能多项式时间验证。所以P⊆NPP⊆NP真正不知道的是PNP?PNP?规约把一个问题翻译成另一个问题理解 NP-hard 和 NP-complete 之前必须先理解规约。规约的意思是把问题 A 的实例在多项式时间内转换成问题 B 的实例并且保持 yes/no 答案一致。记作A≤polyBA≤poly​B意思是A 可以多项式时间规约到 B。也就是说如果我们有一个能解决 B 的算法那么就可以这样解决 A把 A 的输入转换成 B 的输入调用 B 的算法返回 B 的答案所以如果 A≤polyBA≤poly​B那么 B 至少和 A 一样难。A 可以借助 B 来解决所以 B 的能力至少覆盖 A。INDEPENDENT SET 规约到 CLIQUE在无向图中independent set中文常译为“独立集”指的是一组顶点其中任意两个顶点之间都没有边。CLIQUE 刚好相反clique 要求任意两个点之间都有边independent set 要求任意两个点之间都没有边现在有一个问题给定图 GG 和整数 kk问 GG 中是否存在大小为 kk 的 independent set我们可以把它规约到 CLIQUE。做法是构造 GG 的补图 G‾G。补图的意思是原来有边的地方补图里没有边、原来没有边的地方补图里有边于是G 中有大小为 k 的 independent setG 中有大小为 k 的 independent set当且仅当G‾ 中有大小为 k 的 cliqueG 中有大小为 k 的 clique所以INDEPENDENT SET≤polyCLIQUEINDEPENDENT SET≤poly​CLIQUE这个转换显然可以在多项式时间内完成。CLIQUE 规约到 VERTEX COVER在无向图中vertex cover中文常译为“顶点覆盖”指的是一组顶点使得图中每条边至少有一个端点被选中。VERTEX COVER 的判定版是给定图 GG 和整数 kk问 GG 中是否存在大小至少为 kk 的 independent setCLIQUE 可以规约到 VERTEX COVER。核心关系是G 有大小为 k 的 cliqueG 有大小为 k 的 clique当且仅当G‾ 有大小为 n−k 的 vertex coverG 有大小为 n−k 的 vertex cover因为 GG 中的 clique 等价于 G‾G 中的 independent set一个 independent set 的补集就是 vertex cover。所以给定 CLIQUE 实例 (G,k)(G,k)我们可以转换成 VERTEX COVER 实例(G‾,n−k)(G,n−k)如果 VERTEX COVER 的答案是 yes那么原 CLIQUE 的答案也是 yes。3-SAT 规约到 CLIQUE刚刚介绍了 2-SAT。3-SAT 是 SAT 的一个限制版本公式是合取范式每个子句 clause 中包含 3 个文字 literal。一个 literal 可以是变量本身比如 xx也可以是变量的否定比如 ¬x¬x。例如(x∨y∨z)∧(¬x∨y∨w)∧(x∨¬z∨w)(x∨y∨z)∧(¬x∨y∨w)∧(x∨¬z∨w)有些教材把 3-SAT 定义为每个子句“恰好 3 个 literal”有些教材定义为“至多 3 个 literal”。这两个版本都可以证明为 NP-complete差别不影响本文。3-SAT 可以规约到 CLIQUE。构造思路是每个 clause 里的每个 literal 建一个点不同 clause 的两个 literal 如果不冲突就连边冲突的意思是一个是 xx另一个是 ¬x¬x如果公式有 mm 个 clause就问图中是否存在大小至少为 mm 的 clique。为什么这样有效一个大小为 mm 的 clique意味着我们可以从每个 clause 中选出一个 literal并且这些 literal 两两不矛盾。这就对应着一组可以让公式为真的赋值。所以3SAT≤poly⁡CLIQUE3SAT≤poly​CLIQUE这个例子非常经典。NP-hard至少和 NP 中最难的问题一样难一个问题 ΠΠ 是 NP-hard如果NP 中的所有问题都可以多项式时间规约到 ΠΠ。也就是说对于任意 Π′∈NPΠ′∈NP都有Π′≤polyΠΠ′≤poly​Π直观理解NP-hard 问题至少和 NP 里最难的问题一样难。不过 NP-hard 不要求这个问题本身属于 NP。因此 NP-hard 问题可以是判定问题优化问题甚至不是可判定问题MAX-CLIQUEMAX-CLIQUE 是优化问题给定图 GG输出图中最大 clique 的大小。如果你能快速解决 MAX-CLIQUE那么你就能快速解决 CLIQUE 的判定版图 GG 中是否存在大小至少为 kk 的 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-completeNP 里面最难的一批问题NP-complete中文叫 NP 完全。它既可以被多项式时间验证又至少和 NP 中最难的问题一样难。关系可以写成NP-completeNP∩NP-hardNP-completeNP∩NP-hardSAT 是 NP-completeSAT 是给定一个布尔公式是否存在一种变量赋值使公式为真它属于 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≤polyCLIQUE3SAT≤poly​CLIQUE3SAT≤poly3COLORING3SAT≤poly​3COLORING3SAT≤polyHAMILTONIAN PATH3SAT≤poly​HAMILTONIAN PATHCLIQUE 是 NP-complete它属于 NP因为给定一组点可以快速检查它们是否两两相连。它是 NP-hard因为可以从 3-SAT 规约过来。VERTEX COVER 是 NP-complete给定图 GG 和整数 kk问是否存在不超过 kk 个顶点覆盖图中的所有边它属于 NP因为给定一个点集可以快速检查每条边是否至少有一个端点在点集中。它是 NP-hard因为 CLIQUE 可以规约到 VERTEX COVER。3-COLORING 是 NP-complete给定一个无向图问能否用 3 种颜色给所有顶点染色使得任意相邻顶点颜色不同它属于 NP因为给定一种染色方案可以快速检查所有边两端颜色是否不同。它也是 NP-hard可以通过 3-SAT 规约证明。这里有一个很有意思的对比2-COLORING 属于 P3-COLORING 是 NP-complete颜色数只从 2 增加到 3问题难度发生了巨大变化。如何证明一个问题是 NP-complete证明一个问题 ΠΠ 是 NP-complete通常有一个标准模板。证明它属于 NP。首先要证明Π∈NPΠ∈NP也就是如果有一个候选解你可以在多项式时间内验证它。找一个已知 NP-complete 问题规约到它。然后找一个已经知道是 NP-complete 的问题 Π′Π′证明Π′≤polyΠΠ′≤poly​Π意思是已知难问题 Π′Π′ 可以多项式时间转换成当前问题 ΠΠ。这一步说明如果 ΠΠ 容易那么 Π′Π′ 也容易。但 Π′Π′ 已经是 NP-complete所以 ΠΠ 至少也同样难。结合两步骤就得到Π 是 NP-completeΠ 是 NP-complete一定要注意规约方向。要证明当前问题 ΠΠ 很难应该证明已知难问题≤poly⁡Π已知难问题≤poly​Π而不是证明Π≤poly⁡已知难问题Π≤poly​已知难问题后者只能说明当前问题不比已知难问题更难不能证明当前问题也很难。常见的证明路线。很多 NP-complete 证明会形成一条链SAT≤poly3SAT≤polyCLIQUE≤polyVERTEX COVERSAT≤poly​3SAT≤poly​CLIQUE≤poly​VERTEX COVER也可以有3SAT≤poly3COLORING3SAT≤poly​3COLORING3SAT≤polyHAMILTONIAN PATH3SAT≤poly​HAMILTONIAN PATHSUBSET SUM≤polyKNAPSACKSUBSET SUM≤poly​KNAPSACK规约具有传递性。如果A≤polyBA≤poly​B并且B≤polyCB≤poly​C那么A≤polyCA≤poly​C。只要有几个“源头问题”被证明很难后面就可以不断扩展出一整张 NP-complete 问题网络。为什么要区分 P、NP、NP-hard、NP-complete区分这些概念的意义不只是给问题贴标签而是帮助我们判断应该投入什么样的算法努力。如果一个问题属于 P我们通常会继续寻找更快、更省空间、更适合工程实现的精确算法。如果一个问题是 NP-complete那么它很可能不存在多项式时间精确算法。此时更现实的方向包括近似算法不求最优但保证离最优解不太远启发式算法不保证理论最优但在实际数据上效果好随机算法通过随机化获得更好的平均表现剪枝搜索仍然搜索但尽量减少不必要的分支参数化算法当某些参数很小时问题可以高效求解利用特殊结构实际输入可能不是最坏情况。如果一个问题是 NP-hard 但不一定属于 NP比如某些优化问题那么它至少和 NP-complete 问题一样难。我们不能指望一般情况下总能快速求出精确最优解。所以这些分类的作用是帮助我们避免把时间浪费在错误目标上不是所有问题都适合追求“又快、又精确、又通用”的算法。进阶补充伪多项式时间还有一个很容易被忽略的点输入中的数字是如何编码的。