说明

主要来源于算法导论

p类问题

就是能在多项式时间内解决的问题

np类问题

就是能在多项式时间内验证解的问题
p类问题也是np类问题

npc问题

所有np问题都能规约到该问题的问题，并且是一个np问题

hp-hard问题

所有np问题都能规约到该问题的问题，并且不是一个np问题

p != np？

只要能证明任意一个npc问题有多项式解法，就能证明p = np
只要能证明任意一个np类问题没有多项式解法，就能证明p != np