概述

有些计算问题是确定性的，例如加减乘除，只要按照公式推导，按部就班一步步来，就可以得到结果。

但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式能推出下一个质数是多少呢？这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式（polynomial）时间内算出来，就叫做多项式非确定性问题。

NP类问题：所有的非确定性多项式时间可解的判定问题构成NP类问题。

非确定性算法：非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的，算法的验证阶段是确定性的，它验证猜测阶段给出解的正确性。

NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。

而如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NP完全问题（Non-deterministic Polynomial complete problem）。NP完全问题也叫做NPC问题。

生成问题的一个解通常比验证一个给定的解时间花费要多得多。这是这种一般现象的一个例子。与此类似的是，如果某人告诉你，数13,717,421可以写成两个较小的数的乘积，你可能不知道是否应该相信他，但是如果他告诉你他可以因式分解为3607乘上3803，那么你就可以用一个袖珍计算器容易验证这是对的。

完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。

人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们于是就猜想，

这类问题是否存在一个确定性算法，可以在多项式时间内，直接算出或是搜寻出正确的答案呢？

这就是著名的NP=P？的猜想。

在计算机领域，一般可以将问题分为可解问题和不可解问题。不可解问题也可以分为两类：一类如停机问题，的确无解；另一类虽然有解，但时间复杂度很高。可解问题也分为多项式问题(Polynomial Problem，P问题)和非确定性多项式问题(NondeterministicPolynomial Problem，NP问题)。

P问题

P问题是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内判定或解出。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。
确定一个问题是否是多项式问题，在计算机科学中非常重要。已经证明，多项式问题是可解问题，因为除了P问题之外的问题，其时间复杂度都很高，即求解需要大量时间。
理论上有解但其时间复杂度巨大的问题，科学家将其称为难解型问题。对计算机来说，这类问题是不可解的。因此，P问题成了区别问题是否可以被计算机求解的一个重要标志。

NP问题

NP问题是指可以在多项式时间内被非确定机解决的问题。通常它们的时间复杂度都是指数变量，如
等。
这里有一个著名的问题一千禧难题之首。是说P问题是否等于NP问题，也即是否所有在非确定机上多项式可解的问题都能在确定机上用多项式时间求解。这表明用NP问题寻找多项式时间表示的算法很困难，或许最后的结论是NP问题根本就不是P问题。

P=NP?问题

目前已经证明所有P问题都是NP问题，那么反之P—NP吗?这就是所谓的“NP问题”。目前P与NP是否等价是一个既没有证实也没有证伪的问题。但是大部分科学家猜想：找一个问题的解很困难，但验证一个解很容易(证比解易)，用公式表示就是P≠NP。问题较难求解(P)但容易验证(NP)，这与我们的日常生活经验是相符的。

NPC： NP完全性问题

NPC(NP Complete，NP完全)问题
计算机科学家将NP问题中最困难的称为NPC问题。

NPC问题有一个令人惊讶的性质，即

如果一个NPC问题存在多项式时间算法，那么所有NP问题都可以在多项式时间内求解，即P=NP成立。

这是因为每一个NPC问题都可以在多项式时间内转化成任何一个NP问题。只要任意一个NPC问题找到了一个多项式算法，那么所有NP问题都能用这个算法解决，也就解决了NP=P问题。但是给NPC找一个多项式算法太不可想象了，而且也从未成功，因此科学家认为，正是NPC问题的存在，使得人们相信P=NP。

NPC问题目前没有多项式算法，只能用穷举法逐个检验，最终得到答案。但是穷举法的计算时间随问题的复杂程度呈指数增长，很快问题就会变得不可计算了。

围棋或象棋的博弈问题、国际象棋的n皇后问题、密码学中的大素数分解问题等，都属于NPC类问题。

决策树与NP问题

决策树(decision tree)是一种基本的分类与回归方法。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

其主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。
决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。

在决策树算法中，寻找最优决策树是一个NP完全问题。决策树的这一特点，说明我们无法利用计算机在多项式时间内，找出全局最优的解。

也正因为如此，大多数决策树算法都采用启发式的算法，如贪心算法，来指导对假设空间的搜索。可以说，决策树最后的结果，是在每一步、每一个节点上做的局部最优选择。决策树得到的结果，是没法保证为全局最优的。

关于千僖难题

背景
美国麻州的克雷（Clay）数学研究所于2000年5月24日在巴黎法兰西学院宣布了一件被媒体炒得火热的大事：对七个“千僖年数学难题”的每一个悬赏一百万美元。
内容
“千僖难题”之一：P （确定性多项式算法）对NP （非确定性多项式算法）
“千僖难题”之二：霍奇（Hodge）猜想
“千僖难题”之三：庞加莱（Poincare）猜想
“千僖难题”之四：黎曼（Riemann）假设
“千僖难题”之五：杨－米尔斯（Yang-Mills）存在性和质量缺口
“千僖难题”之六：纳维叶－斯托克斯（Navier-Stokes）方程的存在性与光滑性
“千僖难题”之七：贝赫（Birch）和斯维讷通－戴尔（Swinnerton-Dyer）猜想

小结

在设计程序时，我们经常需要评估这个程序的时间复杂度，即衡量当问题规模变大后，程序执行所需的时间增长会有多快。如O(1)表示常数级别，即不管问题的规模变大多少倍，所耗的时间不会改变；O(N2)表示平方级别，即当问题规模增大至2倍时，所花费的时间则放大至4倍；O(2N)表示指数级别，即当问题规模倍数扩大时，所用时间会呈指数放大。

多项式时间则是指O(1)、O(logN)、O(N2)等这类可用多项式表示的时间复杂度，通常我们认为计算机可解决的问题只限于多项式时间内。而O(2N)、O(N!)这类非多项式级别的问题，其复杂度往往已经到了计算机都接受不了的程度。

所有非确定性多项式时间内可解的判定问题构成NP类问题

NP类问题将问题分为求解和验证两个阶段，问题的求解是非确定性的，无法在多项式时间内得到答案，而问题的验证却是确定的，能够在多项式时间里确定结果。

比如：是否存在一个公式可以计算下一个质数是多少？这个问题的答案目前是无法直接计算出来的，但是如果某人给出了一个公式，我们却可以在多项式时间里对这个公式进行验证。

NP中的一类比较特殊的问题，这类问题中每个问题的复杂度与整个类的复杂度有关联性，假如其中任意一个问题在多项式时间内可解的，则这一类问题都是多项式时间可解。这些问题被称为NP完全问题。

可以说NP完全问题是NP类问题的一种特殊情况，总结这几类问题的特点，可参考如下这个表格：