P问题
可以在多项式时间内求解的问题。
“P” 代表 “polynomial time” 。
NP问题
可以在多项式时间内检查解是否合法的问题。
“NP” 代表 “nondeterministic polynomial time” 。
显然有$P\subseteq NP$
归约
对于两个问题A和B，如果能够在多项式时间内对A的输入进行转化，使得解决B的算法能够得到A问题的输出，那么就称A可以归约为B。一个例子是A为求解形式为$ax=b$的方程，而B为求解形式为$ax^2+bx+c=0$的方程。
NPC问题（NP完全问题，NP-Complete问题）
对于一个NP问题，如果所有的NP问题都可以归约为它，那么称之为NPC问题。
NPH问题（NP-Hard问题）
对于一个问题，如果所有的NP问题都可以归约为它，那么称之为NPH问题。
关于3-sat问题
3-sat问题
有若干个布尔型的变量(variable)。
定义文字(literal)为，一个variable(称为positive literal)或者它的取反(称为negative literal)。
定义子句(clause)为，若干个文字（可能是一个）的或。
定义3-sat问题为：给出一个布尔表达式，这个表达式由若干个子句的与构成，每个子句恰好为三个文字的或，问是否存在一种给变量赋值的方式，使得表达式的值为真。
3-sat问题相关的归约
（下面的例子来自维基百科）
表达式$l_1 \vee l_2\vee l_3\cdots\vee l_n$可以归约为3-sat的形式：
已经被证明的重要结论：任意一个NP问题都可以归约为一个3-sat问题。
所以，如果要证明一个问题是NPC问题，则只需要证明它是NP问题且可以由某一个已知为NPC的问题归约到它就可以了。
P=NP?
到目前为止还没有找到在多项式时间内求解NPC问题的算法，也无法将这个命题证明或者证伪。