原创 进阶算法概述
算法分类(多项式分类)
P问题
- 如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。
- P是英文单词多项式的第一个字母。
NP问题
NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题。
NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。
NP问题一直都是信息学的巅峰。巅峰，意即很引人注目但难以解决。在信息学研究中，这是一个耗费了很多时间和精力也没有解决的终极问
题，好比物理学中的大统一和数学中的歌德巴赫猜想等。目前为止这个问题还“啃不动”。但是，一个总的趋势、一个大方向是有的。人们普遍认为，P=NP不成立，也就是说，多数人相信，存在至少一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P≠NP是有原因的，就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题，也即所谓的 NPC问题。C是英文单词“完全”的第一个字母。正是NPC问题的存在，使人们相信P≠NP。
NP-hard
- P!=NP时，NP-hard属于比NP难的问题,只可以用一定运算（时间大于等于多项式运算时间）解决该问题，无法找到多项式的算法。
- P=NP时，NP=NP-hard
NPC问题
- 约化(Reducibility，有的资料上叫“归约”)
: 一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A
参见《算法导论》：一元二次方程解一元一次方程的例子
- 一个问题约化为另一个问题，时间复杂度增加了，问题的应用范围也增大了。
- 通过对某些问题的不断约化，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替复杂度虽然低，但只能用于很小的一类问题的算法。
- 再回想前面讲的P和NP问题，根据约化的传递性，如果不断地约化上去，不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题，那么最后能找到一个时间复杂度最高，并且能“通吃”所有的NP问题的这样一个超级NP问题，就是NPC问题。
- 只要解决了这个NPC问题，那么所有的NP问题都解决了。这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的NPC问题，也就是NP-完全问题。
- NPC问题：
a.它得是一个NP问题；
b.所有的NP问题都可以约化到它。
（证明一个问题是 NPC问题也很简单。先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它