一、基础知识
1.现实中的问题(比如：排序问题)，存在很多解决办法(即计算机领域的算法)，所以需要衡量算法的性能。
一个算法的优劣主要从算法的执行时间(即时间复杂度)和所需要占用的存储空间(即空间复杂度)两个方面衡量。
P类问题和时间复杂度有关，所以本文只谈时间复杂度。
2.时间复杂度
若对排序算法有了解的小伙伴，大多是知道冒泡排序的平均时间复杂度为O( n 2 n^2 n2)，按照多项式的定义(形如 a n ? x n + a n ? 1 ? x n ? 1 + . . . + a 1 ? x + a 0 a_n·x^n + a_{n-1}·x^{n-1} + … + a_1·x + a_0 an??xn+an?1??xn?1+…+a1??x+a0?的式子即为多项式)，所以排序问题存在时间复杂度为O( n 2 n^2 n2)的多项式时间算法，即排序问题属于P问题。
二、P问题
存在多项式时间算法的问题。(P：polynominal，多项式)
当所需计算的数据量小时，人们察觉不到算法时间复杂度分别为O( n n n)与O( 2 n 2^n 2n)的差别，但当数据量达到数百万量级时，O( 2 n 2^n 2n)的算法可能需要让计算机算个几天，甚至数年。
时间复杂度排序 : O ( 1 ) < O ( n ) < O ( log ? 2 n ) < O ( n 2 ) < O ( n a ) < O ( 2 n ) ( a > 2 ) O(1) <O(n) < O(\log_2n) < O(n^2) < O(n^a) < O(2^n) (a > 2) O(1)<O(n)<O(log2?n)<O(n2)<O(na)<O(2n)(a>2)
所以，研究时间复杂度是多项式的算法才有实际意义。
三、NP问题
1.大整数分解
比如：求大整数99400891的2个质因子是困难的，但是若告知9967、9973,验证它们是99400891的2个质因子是可以在多项式时间内实现的。
2.NP问题
存在一类问题，不知道其是否存在多项式时间算法，但可以在多项式时间内验证一个猜测解的正确性。
NP : Nondeterministic polynomial-time 非确定性多项式时间
四、千禧难题之首 : NP=P?
有些科学家认为，所有的NP问题终究都可以在多项式时间内解决，只是我们暂时还没有找到方法；也有些科学家认为，某些NP问题永远无法在多项式时间内解决。
即千禧难题之首 : N P = P ? ? NP=P\,? NP=P?1
如果证明了 N P = P NP = P NP=P就意味着所有的NP问题都可以通过计算机来解决，所以意义重大，不然怎么值100万美元呢(狗头.jpg)
五、NPC问题
1.证明 N P = P ? ? NP=P\,? NP=P?思路之一 ：问题约化
可以用问题B的算法来解决A ，我们就说问题A可以约化成问题B。
例如：
问题A : 3 x + 6 = 12 3x + 6 = 12 3x+6=12 (采用一元一次方程的解法)
问题B : 0 ? x 2 + 3 x + 6 = 12 0·x^2 + 3x + 6 = 12 0?x2+3x+6=12 (采用一元二次方程的解法)
显然问题A可以约化为问题B，如果证明了一元二次方程的解法是多项式时间算法，则说明一元一次方程的解法也是多项式时间算法。
约化具有传递性: A约化为B，B约化为C
因此：
把众多的NP问题层层约化，必定会得到一个或多个“终极问题”，这些约化的终点就是所谓的NPC问题（NP-complete）
2.NPC问题(2个条件)
①自身是NP问题；
②其他NP问题能约化到它；
即：如果所有NP问题可在多项式时间内约化成某个NP问题，则该NP问题称为NP完全问题。
六、NP-hard问题
满足NPC问题的条件②但不满足条件①。
即香港vps : 如果所有NP问题可在多项式时间内约化成某个问题，则该问题称为NP难问题。
显然，NP-hard问题不一定是NP问题，可能是不可判定问题(图灵停机问题)
七、P问题、NP问题、NPC问题和NP-hard问题的关系
八、参考文献
1.P问题、NP问题、NP完全问题和NP难问题
(旅行商问题被科学家证明属于NPC问题)
Latex中的空格 ??
24710454
