Polynomial
Nondeterministic Polynomial
P问题：
一个问题可以在多项式时间复杂度内解决
NP问题：
一个问题可以在多项式时间内证实或者证伪
NP-Hard问题：
对于NP问题在多项式时间内转化为S问题，解决S就可以解决NP，认为S比NP难
转化的过程称为归约，NP---归约--->NP-Hard
NP-Complete问题： 若NP-Hard问题本身也是NP问题，称此问题为NPC问题
P=NP的情况下 P=NP=NPC<NP-Hard
p≠NP的情况下 P<NP<NP-Hard NPC=NP∩NP-Hard
P与NP相等还是不相等的问题是指： 能在多项式时间验证的问题，是指也能在多项式时间内求解的探索？