下载文档原格式
什么是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?）。
np基本引理
NP基本引理（NP-Completeness Theorem）是理论计算机科学中的重要定理之一，也是计算复杂性理论的核心内容之一。
它是由美国计算机科学家Stephen Cook和Leonid Levin于20世纪70年代提出的。
NP基本引理表明，如果一个问题A可以在多项式时间内转化为一个已知的NP完全问题B，那么问题A也是NP完全的。
换句话说，如果我们能够以多项式时间将一个已知的NP完全问题的实例转化为问题A的实例，那么问题A的解决方案的复杂性与NP 完全问题相同。
这个定理的意义在于，它将确定性多项式时间可解（P）和非确定性多项式时间可解（NP）这两个复杂性类联系起来。
NP完全问题是一类特殊的NP问题，被认为是最困难的问题之一，目前还没有有效的多项式时间算法来解决它们。
NP基本引理的证明比较复杂，其中涉及到图灵机的构造和多项式时间归约等概念。
这个定理的提出对计算理论的发展产生了深远的影响，它使得人们能够通过研究一个问题的复杂性来判断其
可解性，并且为算法设计提供了一种方法，即通过将问题归约到已知的NP完全问题上来证明其复杂性。
NP问题NP完全问题（NP-completeproblem）如何判断是否是NP完全问题在算法复杂度分析的过程中，⼈们常常⽤特定的函数来描述⽬标算法，随着变量n的增长，时间或者空间消耗的增长曲线，近⽽进⼀步分析算法的可⾏性（有效性）。
引⼊了Big-O，Big-Ω，来描述⽬标算法的上限、下限复杂度函数。
⽤Big-Θ描述和⽬标函数同序的复杂度函数，即由Big-Θ既是上限也是下限。
常常⽤到如下时间复杂度函数标度1, log n, n, n log n, n^2, 2^n, n!通常将具有n^x，x为正整数形式的时间复杂度函数称为多项式复杂度。
通常认为具有多项式时间复杂度的算法是容易求解的。
超过多项式时间复杂度，算法增长迅速，不易求解。
下图将展⽰NP和NP完全问题在所有问题中的位置。
通常问题分为可解决（Solvable）和不可解决（Unsolvable）。
可解决问题⼜可以分为易解决（Tractable）、不易解决（Intractable）和不确定是否容易解决（NP）可解决（Solvable）是指存在算法能够解决的问题不可解决（Unsolvable）是指不存在解决该问题的算法，如The Halting Problem。
易解决（Tractable），即P问题，是指具有最坏时间复杂度为多项式时间的算法能够解决的问题不易解决（Intractable）是指不存在最坏时间复杂度为多项式时间的算法能够解决的问题不确定是否容易解决（NP），还未被证明是否存在多项式算法能够解决这些问题，⽽其中NP完全问题⼜是最有可能不是P问题的问题类型。
判断是否是NP完全问题1.元素较少时算法的运⾏速度⾮常快，但随着元素数量的增加，速度会变的⾮常慢。
2.涉及所有组合问题通常是NP完全问题3.不能将问题分成⼩问题，必须考虑各种情况，这可能是NP问题4.如果问题涉及序列（如旅⾏商问题中的城市序列）且难以解决，它可能是NP问题5.如果问题涉及集合（如⼴播电台集合）且难以解决，它可能是NP完全问题6.如果问题可转化为集合覆盖问题或商旅问题，那它肯定是NP问题。
