P,NP,NPC,NP-Hard
P问题：可以通过确定性图灵机在多项式时间内求解。
NP问题：可以通过非确定性图灵机在多项式时间内求解。
或者说，可以在多项式时间内验证一个解。
NP问题的例子，Hamilton回路（在图中找一条环路，它经过且只经过一次每一个点）。
非NP问题，无法在多项式时间内验证解。例子：问一个图是否不存在Hamilton回路。（除非穷举所有可能，否则无法验证）
NPC问题的定义：它满足如下两个条件：
1.是NP问题。
2.所有的NP问题都能规约为它。
俗语就是，到现在还找不到多项式时间解法的NP问题，只能用指数级甚至阶乘级的复杂度的搜索。
因为所有的NP问题都能规约为NPC问题，如果一个NPC问题存在多项式时间的解法，那么会得出P=NP=NPC，所以，目前人们不相信NPC问题存在多项式时间的解法。
NPC问题的例子：逻辑电路问题。给定一个逻辑电路（比如输入接上若干与非门），是否存在一个输入使其输出为True？
NP-Hard问题：所有的NP问题都能规约到它，但它不一定是NP问题。