NP问题
1.定义
- P类问题：所有可以在多项式时间内求解的判定问题构成P类问题。
- 判定问题：判断是否有一种能够解决某一类问题的能行算法的研究课题。
- NP类问题：所有的非确定性多项式时间可解的判定问题构成NP类问题。（或者说能在多项式时间内验证解是否正确。）
- 非确定性算法：非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的，算法的验证阶段是确定性的，它验证猜测阶段给出解的正确性。
- P类问题和NP类问题的关系：
- NPC问题：NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的——这些问题被称为NP-完全问题(NPC问题)。
2.关系
1971年，斯蒂芬·库克发表了“定理证明过程的复杂性”。把以多项式时间解决为衡量标准的问题归成三大类，即NP，NP完全与NP难度问题。
3.时间复杂度
- 时间复杂度：随着问题规模n扩大，所需时间的增长有多快
- 时间复杂度不是代表解决问题所花费的具体时间，而是指随着问题规模的扩大，所需时间的增长速度。
即下图所代表的斜率。
4.常见问题的时间复杂度
- O(1) : 高斯求和
- O(n) : 求数组最大值
- O(n2) : 冒泡排序
- O(nlogn) : 希尔排序
5.如何比较时间复杂度的大小
例如：100n的平方和n的三次方
由图可知：随着问题规模的不断增大，n的三次方的增长速度明显大于100n的平方。
结论：O(1)<O(logn)<O(n的k次) <O(a的n次)<O(n!){前三项多项式级复杂度，后两项是非多项式级}
6.规约
利用规约的思想，我们可以想象我们可以把所有的NP问题都规约成“超级问题”，这要我们找到解决这个“超级问题”的方法，我们就可以解决所有问题了。——这就是NPC问题的由来。