http://zh.wikipedia.org/w/index.php?title=NP%E5%AE%8C%E5%85%A8&variant=zh-tw 在计算复杂度理论的世界中，NPC问题是NP（非决定性多项式时间）中最难的决定性问题 。因此NP完备问题应该是最不可能被化简为P（多项式时间可决定）的决定性问题的集合 。许多人推测P与NPC没有交集。理由是因若任何NPC问题得到多项式时间的解法，那此解 法就可应用在所有NP问题上。 一个决定性问题C若是为NPC，则代表它对NP是完备的，这表示: 它是一个NP问题，且 它是一个NP-困难问题，意即其他属於NP的问题可变换（reducible）成它。 可变换在此意指对每个问题L，总有一个多项式时间多对一变换，即一个决定性的演算法 可以将实例l ∈ L 转化成实例c ∈ C，并让c 回答Yes若且为若此答案对l 也是Yes。为 了证明某个NP问题A实际上是NPC问题，证明者必须找出一个已知的NPC问题可以变换成A。 本定义的得到一个结论，就是若上述的C有一个多项式时间可解的演算法，则我们可以将 所有的NP问题降到P之中。 这个定义是史提芬‧古克[1]所提出。虽然NPC这个词并没有出现在这篇论文上任何地方。 在这个资讯科学会议上，资讯科学家激动地讨论NPC问题是否可以在一个确定型图灵机上 以多项式时间求解。John Hopcroft总结与会众人的共识，认为由於没有人能对某一命题 提出驳倒对方的证明，此问题不会於现在解决。此命题就是知名的 P和NP相等吗?。 尚未有人能提出证明，说明NPC问题是否能在多项式时间中解决，使得此问题成为着名的 数学中未解决的问题。 剑桥大学的「克雷数学研究所」（Clay Mathematics Institute, 简称CMI）提供了一百万美金奖金给任何可以证明P=NP或P≠NP的人。 一开始很难相信NPC问题是实际存在的，但着名的古克-李芬定理说明了一切（由Leonid Levin与Cook独立证出SAT问题是NPC问题，简化过但依旧艰深的证明在此）。 在1972年，Richard Karp证明有好几个问题也是NPC（请见Karp的21个NP完全问题），因 此除了SAT问题外，的确存在着一整类NPC问题。从古克开始，数千个问题藉由从其他NPC 问题变换而证实也是NPC问题，其中很多问题被蒐集在Garey与Johnson於1979年出版的书 之中[2]。 一个满足条件2但不满足条件1的问题被称为NP-hard。正式地说，一个NP-hard问题至少跟 NPC问题一样难，也许更难！例如在某些任意大的棋盘游戏走出必胜的下法，就是一个 NP-hard的问题，这个问题甚至比那些NPC问题还难！ 范例问题 另一个有趣的例是图同构(isomorphism)问题，即以图论方法决定两个图是否为同构。两 图同构的直觉条件是若其中一图可以经由移动顶点使它与另一个图重合，则为同构。 思 考下列两问题： 图同构：图G1是否与图G2同构？ 子图同构：图G1是否与图G2的任一子图同构？ 子图同构问题是NPC，而图同构问题一般认为不是P也不是NPC问题，虽然它明显是一个NP 问题。这是一个典型被认为很难却还不是NPC问题的例子。 想要证明一个问题是NPC，最简单的方法是先证明它属於NP，然後将它变换成某个已知是 NPC的问题。因此在学习变换技巧前，先熟悉各种不同类型的NPC问题是很有用的。下表列 出了一些以决定性命题表示的着名NPC问题： 变换流程图。布林满足问题:（Boolean satisfiability problem）（SAT） N-puzzle问题（华容道问题):(N-puzzle） 郊游打包问题:（Knapsack problem） 汉弥尔顿回圈问题:（Hamiltonian cycle problem） 旅行推销员问题:（Traveling salesman problem） 子图同构问题:（Subgraph isomorphism problem） 子集合加总问题:（Subset sum problem） 分团问题:（Clique problem） 顶点涵盖问题:（Vertex cover problem） 独立顶点集问题:（Independent set problem） 图着色问题（参见四色定理）:（Graph coloring 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机器拥有大量通用暂存器， 因此启发式演算法很适合用来解这类题目。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.224.53.178