预备知识
衡量程序的好坏不是用特定的数据量来衡量，而是数据的规模变大到几百倍后，程序运行的时间是否相同。
举例：数据增大两倍，时间增大4倍，那么属于O(n^2)的复杂度。
分类：
- 多项式级 O(1),O(log(n)),O(n^a)
- 非多项式级别 O(a^n)和O(n!)
P类问题
一个问题可以找到一个在多项式时间内解决的算法
NP类问题
指在多项式时间内验证一个解的问题/猜出一个解。
（类似于存在性问题，比如问A到B是否有一条长度为100的路）
关系
显然，所有的P问题都是NP问题，但P=NP是关注的焦点。
NPC问题
规约：问题A可规约为问题B，即指可以用B的解法来解A，或者说问题A可以变为问题B。
举例：一元一次方程可以规约为一元二次方程。原因在于只要加上系数为0的二次项即可。
意义：B的时间复杂度 > A的时间复杂度；具有传递性
不断提升时间复杂度，存在一类（许多个）NP问题，能够让所有的NP问题转化为它。即NP-C问题。
当想要表达一个问题不存在多项式的高效算法时，就说这个问题属于NPC问题。
NPC问题两个要求
- 是一个NP问题
- 所有的NP问题能规约到它
那么如果一个NPC问题找到多项式解法，所有的NP问题就能用这个算法解决了。因此正是由于NPC的存在，所以P≠NP。（如果证明了P=NP，那么证明一个解和验证一个解一样容易）
NP-Hard问题
只满足NPC问题的第二条
放宽了条件，比NPC问题更难解决。