在P问题与NP问题上的一个重大进展在20世纪70年代初由Cook S和Levin L完成.他们发现NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的.这些问题被称为NP-完全问题(NPC问题).

判定方法:

一个判定性问题，满足：

(1)∏∈NP

(2)对任意一个∏’∝poly∏ (注:poly为规约符号)

则问题∏称为NP-完全的(NP-complete，NPC)；如果问题∏仅满足条件(2)而不满足条件(1)，则问题NP称为NP-难的(NP-hard)。