算法分析与设计 —— NP完全性理论
确定性算法和非确定性算法
（1）确定性算法：整个执行过程中每一步都只有一个选择，则称A是确定性算法。对同样的输入，输出结果一定相同。
（2）非确定性算法：在每一时刻，根据当时的状态和输入，若机器有多个动作可供选择，第一个获得结束的成功选择使算法终止，此时称算法为非确定性的。
P类问题
用一个确定性算法在多项式时间内可解的问题。
（1） P类问题是NP问题的子集（如果P类问题既然能在多项式时间内求解，也必然能在多项式时间在验证它的解）
NP类问题
能在多项式时间内验证得出一个正确解的问题。
（1）对于哈密尔顿回路问题，如果给出一个任意的回路，我们可以很容易的判断出该回路是否是哈密尔顿回路（看是不是所有顶点都在回路中)，故哈密尔顿回路是NP问题。
约化
（1）一个问题A可以约化成问题B的含义即是，可以用解决问题B的解法来解决问题A，或者说，问题A可以“变成”问题B。如：一元一次方程可以“约化”为一元二次方程
（2）问题A可“约化”为问题B的直观意义：B的时间复杂度高于或等于A的时间复杂度。也就是说，问题A不比问题B难
（3）约化具有传递性：如果问题A可约化成问题B，问题B可约化成问题C，则问题A一定可约化成问题C
（4）约化需要在多项式时间内完成
NP完全问题（NPC）
存在这样一个NP问题，所有的NP问题都可以在多项式时间内约化成它，则这个问题是NPC问题。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。
（1）NPC问题是NP问题的子集。
（2）目前为止我们还不能证明NPC问题有多项式算法（即NP等于P），也不能证明NPC问题没有多项式算法（即NP不等于P）。因此，我们一般认为NPC问题是难解问题。
（3）如何证明一个新问题A是NPC问题
-
证明A∈NP；
-
选取一个已知的NPC问题B；
-
构造一个从B到A的变换f；
-
证明f为一个多项式变换。
（4）哈密尔顿回路也是NPC问题，但尚未被解决。（通过上述证明过程可被证明）
NP难问题（NPH）
存在这样一个NPC问题，所有的NPC问题都可以在多项式时间内约化成它，则这个问题是NPH问题