NP完全

描述P, NP, NP完全，以及NP困难之间关系的欧拉图

NP完全或NP完备 （NP-Complete，缩写为NP-C或NPC），是计算复杂度理论中，决定性问题的等级之一。NP完备是NP与NP困难问题的交集，是NP中最难的决定性问题，所有NP问题都可以在多项式时间内被归约（reduce to）为NP完全问题。倘若任何NP完全问题得到多项式时间内的解法，则该解法就可应用在所有NP问题上，亦可证明NP问题等于P问题，然而目前为止并未发现任何能在多项式时间内解决NP完全问题的方法。

正式定义

假设P ≠ NP的复杂度类的图解。若P = NP则三类别相同。

一个决定性问题C若是为NPC（NP完全），则代表它对NP是完全的，这表示：

1. 它是一个NP问题
2. 它是一个NP困难问题
3. 其他属于NP的问题都可在多项式时间内归约（reduce to）成它。

可归约（reducible）在此意指对每个问题L，总有一个多项式时间多对一变换，即一个决定性的算法可以将实例l ∈ L转化成实例c ∈ C，并让c回答Yes当且仅当此答案对l也是Yes。为了证明某个NP问题A实际上是NP完全问题，证明者必须找出一个已知的NP完全问题可以归约成A。

本定义得到一个结论，就是若上述的C有一个多项式时间可解的算法，则我们可以将所有的NP问题降到P之中。若欲证明一个问题是NPC，最简单的方法是先证明它属于NP，然后将“某个已知是NPC的问题”归约成它。

历史

前述定义是史提芬·古克^[1]所提出。虽然NPC这个词并没有出现在这篇论文上任何地方。在这个信息学会议上，信息学家激动地讨论NPC问题是否可以在一个确定型图灵机上以多项式时间求解。John Hopcroft总结与会众人的共识，认为由于没有人能对某一命题提出驳倒对方的证明，此问题不会于现在解决。此命题就是知名的

P和NP相等吗？。尚未有人能提出证明，说明NPC问题是否能在多项式时间中解决，使得此问题成为著名的数学中未解决的问题。位于美国麻省剑桥市的“克雷数学研究所”（Clay Mathematics Institute，简称CMI）提供了一百万美元奖金给任何可以证明P=NP或P≠NP的人。

一开始很难相信NPC问题是实际存在的，但著名的古克-李芬定理说明了一切（由Leonid Levin与Cook独立证出SAT问题是NPC问题（即Cook-Levin理论）。

在1972年，理查德·卡普证明有好几个问题也是NPC（请见卡普的二十一个NP-完全问题），因此除了SAT问题外，的确存在着一整类NPC问题。从古克开始，数千个问题借由从其他NPC问题变换而证实也是NPC问题，其中很多问题被搜集在Garey与Johnson于1979年出版的书之中^[2]。

满足条件2（无论是否满足条件1）的问题集合被称为NP困难。一个NP困难问题至少跟NPC问题一样难。有一类问题已经被证明属于NP困难但不属于NP，即，这类问题至少与NP-complete一样难，但这类问题又不属于NP（自然也不属于NP-complete）。例如围棋的必胜下法，就是这样一个问题。

例子

子集合加总问题

一个NPC问题的例子是子集合加总问题，题目为

给予一个有限数量的整数集合，找出任何一个此集合的非空子集且此子集内整数和为零。

意即：$S$是一个包括若干整数的集合，找出任一一个$S'\subset S$且$\sum _{x\in S'}x=0$

这个问题的答案非常容易验证，但目前没有任何一个够快的方法可以在合理的时间内（意即多项式时间）找到答案。只能一个个将它的子集取出来一一测试，它的时间复杂度是$O(2^{n})$，$n$是此集合的元素数量。

图同构问题

另一个有趣的例是图同构（isomorphism）问题，即以图论方法决定两个图是否为同构。两图同构的直觉条件是若其中一图可以经由移动顶点使它与另一个图重合，则为同构。思考下列两问题：

• 图同构：图G₁是否与图G₂同构？
• 子图同构：图G₁是否与图G₂的某一子图同构？

子图同构问题是NPC，而图同构问题一般认为不是P也不是NPC问题，虽然它明显是一个NP问题。这是一个典型被认为很难却还不是NPC问题的例子。

其他

下表列出了一些以决定性命题表示的著名NPC问题：

变换流程图。

• 布尔可满足性问题
• N-puzzle问题（华容道问题）
• 背包问题
• 汉弥尔顿循环问题
• 旅行推销员问题
• 子图同构问题：（Subgraph isomorphism problem）
• 子集合加总问题
• 分团问题
• 顶点覆盖问题：（Vertex cover）
• 独立顶点集问题：（Independent set problem）
• 图着色问题
• 扫雷

更多NPC问题的例子，请见NP-complete问题列表。

右边是一些NPC问题及证明其为NPC问题的变换流程图。在流程图中，箭头代表的是从何问题变换成另一问题的过程，要注意的是这张图并不代表这些问题的数学关系，事实上任两个本质为NPC的问题都可以以多项式时间变换，这图仅指示可以让研究者较为简单地变换问题的顺序。

通常一个P与NPC问题的叙述看起来只有一些不同的地方，例如3SAT问题（SAT问题的限制版本）仍然是NPC问题，但更限制的2SAT问题则是个P问题（准确的说，是NL-complete问题），而条件较为宽松的MAX 2SAT问题却又成了NPC问题。决定一个图是否能被两色涂满是P问题，但三色图是NPC问题，即使我们将它限制在平面图上。决定一个图有无循环或它是两分图很容易（在log空间等级），但是发现一个最大二分图或最大循环子图则是NPC。以一固定百分比来求郊游打包问题的最佳解可以在多项式时间解决，但是求最佳解是NPC。

折衷的解法

目前为止，所有已知解NPC问题的算法需要依照资料数量而定的超多项式（superpolynomial）时间，目前也不知道是否有任何更快的算法存在。因此要在输入资料量大的时候解决一个NPC问题，通常我们使用下列的手段来解：

• 近似算法：这类算法可以快速发现离最佳解在一定差距内的次佳解。
• 随机数算法：此类算法可提供一随机数产生的输入资料，让本质上解答分布均匀的受测程序可以有良好的求解效率。对于解答分布不均匀的程序，则可以降低随机数程度以改变输入资料。
• 特例：此算法可以在题目呈献某些特殊情况时快速得解。参数化复杂度（Parameterized complexity）可视为广义的此类算法。
• 启发式算法：这种算法在许多时候可以产生理性解答（即运用评比或线索找出解），但无法保证它效率的良莠与解答的好坏程度。一个启发式算法的例子是用在图着色问题以O（n log n）的贪心算法找次佳解，用在某些编译器的寄存器配置阶段上，此技术又叫图着色全局寄存器配置（graph-coloring global register allocation）。每顶点视为一变量，每边代表两变量同时使用的情况，颜色则代表配置给每一变量的寄存器编号。由于大多数的RISC机器拥有大量通用寄存器，因此启发式算法很适合用来解这类题目。

其他归约法

依照上述NPC的定义，所谓的归约（reduce to）其实是多项式时间多对一变换的简称。

另一种归约法称为多项式时间图灵归约（polynomial-time Turing reduction）。若我们提供一个副函数（subroutine）可以在多项式时间解出"Y"，又可写出调用此副函数的程序并在多项式时间解出问题"X"，代表我们可以将"X"多项式时间图灵变换成"Y"。相较起来，不同处在于多对一变换只能调用上述副函数一次，且副函数的回传值必须就是整个变换程序回传的值。

如果有人使用图灵变换而非多对一变换来解析NPC，此问题的解答集合不一定会小于NPC。孰大孰小其实是个开放问题。如果两个概念相同，则可导出NP=反NP（co-NP）。此结论成立的道理在于NPC与反NPC的定义以图灵归约来看是相等的，且图灵变换定义的NPC包含多对一变换定义的NPC，反NPC也是相同情况。所以若是两种变换定义的NPC一样大的话，反NPC也会比照办理（在两者的定义之下）。例如SAT的反问题也会是NPC（在两者的定义之下）。因此推得NP = 反NP（证明在反NP条目中）。虽然NP是否等于反NP是个开放问题，但一般认为这似乎不大可能，也因此那两类的NPC定义也不大可能相等。

另一种很常用于NPC证明的归约手法是对数空间多对一变换（logarithmic-space many-one reduction），它是一种可以在对数量级空间运用的多对一变换法。由于每道可以在对数空间完成的运算也可以在多项式时间做完，因此能使用对数空间多对一变换的场合也可以使用多项式时间多对一变换。本方法较多项式时间多对一变换优雅，它也可以让我们对算法复杂度细分出更多分类，例如P完全复杂度。而NPC的定义是否会因为使用不同变换手法而产生差异，仍是一个未知的问题。

参见

• NP-complete问题列表
• 几乎完全问题与弱完全问题
• ASR-complete
• Ladner理论
• NP困难
• P/NP问题
• 三维匹配问题

参考文献

书籍

• ^ S. A. Cook. The complexity of theorem proving procedures, Proceedings, Third Annual ACM Symposium on the Theory of Computing. New York: ACM. 1971: 151–158. 
• ^ Garey, M.; D. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. 1979. ISBN 978-0-7167-1045-5. （此书是发展此理论及集多种问题的经典）
• Paul E. Dunne. An Annotated List of Selected NP-complete Problems. The University of Liverpool, Dept of Computer Science, COMP202. [2006-11-23]. （原始内容存档于2006-11-25）. 
• Pierluigi Crescenzi; Viggo Kann; Magnús Halldórsson; Marek Karpinski; Gerhard Woeginger. A compendium of NP optimization problems. Stockholm: KTH NADA. [2006-11-23]. （原始内容存档于2006-12-05）. 
• Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. NP-Completeness. Introduction to Algorithms Second. MIT Press and McGraw-Hill. 2001: 966-1021. ISBN 978-0-262-03293-3. 
• Michael Sipser. NP-completeness, Additional NP-complete Problems. Introduction to the Theory of Computation. PWS Publishing. 1997: 248-271. ISBN 978-0-534-94728-6. 
• Christos Papadimitriou. NP-complete problems. Computational Complexity 1st. Addison Wesley. 1993: 181–218. ISBN 978-0-201-53082-7. 

网页

• Computational Complexity of Games and Puzzles（页面存档备份，存于互联网档案馆）
• Tetris is Hard, Even to Approximate
• Minesweeper is NP-complete!