NP完全问题

设A、B是自然数集，如果存在确定型图灵机多项式时间有界可计算的函数k(x)(即k(x)∈P，参见P=NP问题)使

x∈B 当且仅当 k(x)∈A，

则称B可在多项式时间内归约到A，记作

B≤A

(显然，若B≤A则B≤A)。如果B≤A，就称判定问题“x∈B”可以在多项式时间内归约到判定问题“x∈A”。

设A∈NP(A是非确定型图灵机多项式时间有界可计算的)，如果对每个B∈NP都有

B≤A，

则称集合A(判定问题“x∈A”)是NP完全的集合(问题)。

NP完全问题可以看作NP类中最复杂的问题。要证明P=NP，只要证明某个NP完全问题是属于P的就可以了。反之，要证明P≠NP，也只需证明某个NP完全问题不属于P就可以了。

1971年，S．库克发现了第一个NP完全问题，他证明：命题公式的可满足性问题是NP完全的。此后二十年中，人们已经找到了数百个NP完全问题。M．R．加里和D．S．约翰逊所著的《计算机与难解性》一书对NP完全问题作了详尽的叙述，并列举了数百个NP完全问题的实例。(参见P=NP问题。)