NP-Complete

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

1. 它是一个NP问题，且
2. 其他属于NP的问题都可归约成它。

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

本定义得到一个结论，就是若上述的C有一个多项式时间可解的算法，则我们可以将所有的NP问题降到P之中。

这个定义是史提芬·古克所提出。虽然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（请见卡普的二十一个NP-完全问题），因此除了SAT问题外，的确存在着一整类NPC问题。从古克开始，数千个问题借由从其他NPC问题变换而证实也是NPC问题，其中很多问题被搜集在Garey与Johnson于1979年出版的书之中。

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