下载文档原格式
什么是NP完全问题在学习决策树的时候，我们知道，其⼀⼤特点是：寻找最佳的决策树是NP完成问题。
什么是NP完全问题，决策树的这⼀特点⼜是什么意思？什么是NP完全问题这⾥的NP其实是Non-deterministic Polynomial的缩写，即多项式复杂程度的⾮确定性问题，NP完全问题有时也会简称为NP-C问题。
与此概念相关的还有P类问题、NP类问题等。
要理解什么是NP完全问题，⾸先得从P类问题开始理解。
所有可以在多项式时间内求解的判定问题构成P类问题在设计程序时，我们经常需要评估这个程序的时间复杂度，即衡量当问题规模变⼤后，程序执⾏所需的时间增长会有多快。
如O(1)表⽰常数级别，即不管问题的规模变⼤多少倍，所耗的时间不会改变；O(N2)表⽰平⽅级别，即当问题规模增⼤⾄2倍时，所花费的时间则放⼤⾄4倍；O(2N)表⽰指数级别，即当问题规模倍数扩⼤时，所⽤时间会呈指数放⼤。
多项式时间则是指O(1)、O(logN)、O(N2)等这类可⽤多项式表⽰的时间复杂度，通常我们认为计算机可解决的问题只限于多项式时间内。
⽽O(2N)、O(N!)这类⾮多项式级别的问题，其复杂度往往已经到了计算机都接受不了的程度。
所有⾮确定性多项式时间内可解的判定问题构成NP类问题NP类问题将问题分为求解和验证两个阶段，问题的求解是⾮确定性的，⽆法在多项式时间内得到答案，⽽问题的验证却是确定的，能够在多项式时间⾥确定结果。
⽐如：是否存在⼀个公式可以计算下⼀个质数是多少？这个问题的答案⽬前是⽆法直接计算出来的，但是如果某⼈给出了⼀个公式，我们却可以在多项式时间⾥对这个公式进⾏验证。
NP中的⼀类⽐较特殊的问题，这类问题中每个问题的复杂度与整个类的复杂度有关联性，假如其中任意⼀个问题在多项式时间内可解的，则这⼀类问题都是多项式时间可解。
这些问题被称为NP完全问题。
可以说NP完全问题是NP类问题的⼀种特殊情况，总结这⼏类问题的特点，可参考如下这个表格：问题类型是否能在多项式时间内求解是否能在多项式时间内验证P是是NP是 or 否是NP-C未知是注：表格中的问题类型的困难程度依次递增由表可知，NP类问题是否能在多项式时间内求解，其答案并不明确，如果回答为「是」，岂不是跟P类问题⼀样了？值得⼀题的是，P=NP？是千禧七⼤难题的⾸个难题，是⼀个价值百万美元的问题，这个问题本质是求证：能⽤多项式时间验证解的问题是否内在多项式时间内找出解。
算法----NP-难度和NP-完全的问题1、确定的算法算法运算的结果都是唯⼀确定的, 这样的算法叫做确定的算法(deterministic algorithm) 。
如加减乘除2、不确定的算法允许算法每种运算的结果不是唯⼀确定的, ⽽是受限于某个特定的可能性集合。
执⾏这些运算的机器可以根据终⽌条件选择可能性集合中的⼀个作为结果。
这就引出了所谓不确定的算法( nondeterministic algorithm)。
如求下⼀个⼤质数3、不确定机式执⾏不确定算法的机器称为不确定机(nondeterministic machine ) 。
然⽽, 这⾥所定义的不确定机实际上是不存在的, 因此通过直觉可以感到这类问题不可能⽤“快速的”确定算法求解。
4、P问题（Polynomial多项式问题）P 是所有可在多项式时间内⽤确定算法求解的判定问题的集合。
5、NP问题（Non-Deterministic Polynomial, ⾮确定多项式）NP是所有可在多项式时间内⽤不确定算法求解的判定问题的集合。
有些问题很难找到多项式时间的算法（或许根本不存在），例如“找出⽆向图中”问题。
但如果给了该问题的⼀个答案，可以在多项式时间内判断这个答案是否正确。
例如说对于哈密顿回路问题，给⼀个任意的回路，很容易判断它是否是哈密顿回路（只要看是不是所有的顶点都在回路中就可以了）。
这⾥给出NP问题的另⼀个定义,这种可以在多项式时间内验证⼀个解是否正确的问题称为NP问题，亦称为验证问题类（布尔判断问题）。
6、约化令 L1 和L2 是两个问题, 如果有⼀确定的多项式时间算法求解L1 , ⽽这个算法使⽤了⼀个在多项式时间内求解L2 的确定算法,则称L1 约化为L2 ( 也可以写作L1 ∝L2 )。
7、NP-完全问题如果可满⾜性约化为⼀个问题L,则称此问题L是NP-难度的。
如果L是NP难度的且L∈NP, 则称问题L是NP-完全的。
⼀切NP-完全的问题都是NP-难度的问题, 但⼀切NP-难度的问题并不都是NP-完全的。
P/NP问题一个NP－完全的问题具有如下性质：它可以在多项式时间内求解，当且仅当所有的其他的NP－完全问题也可以在多项式时间内求解。
P是所有可在多项式时间内用确定算法求解的判定问题的集合。
NP问题是所有可用多项式时间算法验证其猜测准确性的问题的集合。
令L1和L2是两个问题，如果有一确定的多项式时间算法求解L1，而这个算法使用了一个在多项式时间内求解L2的确定算法，则称L1约化为L2。
如果可满足性约化为一个问题L，则称L问题是NP-难度的。
如果L是NP难度的且L（－NP，则称L是NP－完全的。
NP并不是NON-POLYNOMIAL，把NP说成是NON -POLYNOMIAL，是望文生义，读书不求甚解。
事实上，如果你能够证明某个NP问题是个NON-POLYNOM IAL的问题，你就可以去领那七个百万美元数学大奖中间的一个了。
数学上著名的NP问题，完整的叫法是N P完全问题，也即“NP COMPLETE”问题，简单的写法，是NP=P？的问题。
问题就在这个问号上，到底是NP等于P，还是NP不等於P。
证明其中之一，便可以拿百万美元大奖。
这个奖还没有人拿到，也就是说，NP问题到底是Polynomial，还是Non-Polynomial，尚无定论。
Mr. X信口开河敢说NP就是Non-Polyno mial，真是不知天高地厚，惹人笑话。
NP里面的N，不是Non-Polynomial的N，是Non-Deterministic，P代表Polynomial倒是对的。
NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。
P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被“克雷数学研究所”（Cl ay Mathematics Institute, 简称CMI）在千禧年大奖难题中收录。
P/NP问题中包含了复杂度类P与NP 的关系。
1971年史提芬〃古克(Stephen A. Cook) 和Leonid Levin 相对独立的提出了下面的问题,即是否两个复杂度类P和NP是恒等的（P=NP?）。
