复杂度级别: 1)多项式级别O(n^k);2)非多项式级别，如，指数级O(a^n)和阶乘级别O(n!)。后者的复杂度无论如何都大于前者。归约(约化)：如果能找到这样一个多项式变换法则，对任意一个程序A的输入，都能按这个法则变换为程序B的输入，使两程序的输出相同，那么我们说，问题A可归约为问题B。 通俗解释：一个问题A可以归约为问题B指，可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。特点：“问题A可归约为问题B”有一个直观意义，B的时间复杂度高于或者等于A的时间复杂度，既，问题A不比问题B难。性质：传递性。如果问题A可以归约为问题B，问题B可以归约为问题C，则问题A一定可以归约为问题C。P问题， NP问题， NPC问题， NP-hard问题的定义和相互关系P问题(polynomial)：求解一个问题的时间复杂度是多项式级别NP问题(nondeterministic polynomial)：可以在多项式时间里验证解是否正确的问题。定义NP问题的意义在于，如果一个问题不能在多项式时间验证，则这个问题一定没有多项式时间的算法。 图中某条路是否是Hamilton回路，可以在多项式时间验证，是NP问题图中是否不存在Hamilton回路，不可以在多项式时间验证。NPC问题(nondeterministic polynomial complete)： 定义：一个问题1）它是NP问题；2）所有的问题都可以约化到它，这样的问题称为NPC问题。证明：1）先证明它是NP问题；2）再证明其中一个已知的NPC问题能约化到它（由约化的传递性，如果A能约化到B，则B的时间复杂度不低于A）。特点：NPC问题目前没有多项式的有效解法，只能有指数级或阶乘级复杂度的算法搜索NP-hard问题(nondeterministic polynomial - hard)：满足NPC问题的第2条但是不一定满足第1条。即使NPC问题获得了多项式级别的求解算法，NP-hard问题可能仍然找不到多项式级的算法。他们之间的关系： P问题一定是NP问题，当前无法证明NP问题是否是P问题。但普遍认为P≠NP。于是NP问题包含P问题。NP问题可以归约为NPC问题，所以NP问题包含NPC问题
