下载文档原格式
NP完全的问题一个NP－完全的问题具有如下性质：它可以在多项式时间内求解，当且仅当所有的其他的NP－完全问题也可以在多项式时间内求解。
P是所有可在多项式时间内用确定算法求解的判定问题的集合。
NP 问题是所有可用多项式时间算法验证其猜测准确性的问题的集合。
令L1和L2是两个问题，如果有一确定的多项式时间算法求解L1，而这个算法使用了一个在多项式时间内求解L2的确定算法，则称L1约化为L2。
如果可满足性约化为一个问题L，则称L问题是NP-难度的。
如果L是NP难度的且L（－NP，则称L是NP－完全的。
NP并不是NON-POL YNOMIAL，把NP说成是NON-POL YNOMIAL，是望文生义，读书不求甚解。
事实上，如果你能够证明某个NP问题是个NON-POL YNOMIAL的问题，你就可以去领那七个百万美元数学大奖中间的一个了。
数学上著名的NP问题，完整的叫法是NP完全问题，也即“NP COMPLETE”问题，简单的写法，是NP=P？的问题。
问题就在这个问号上，到底是NP等于P，还是NP不等于P。
证明其中之一，便可以拿百万美元大奖。
这个奖还没有人拿到，也就是说，NP 问题到底是Polynomial，还是Non-Polynomial，尚无定论。
NP里面的N，不是Non-Polynomial的N，是Non- Deterministic，P代表Polynomial倒是对的。
NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。
如果一个判定性问题的复杂度是该问题的一个实例规模n的多项式函数，则这种可以在多项式时间内解决的判定性问题属于P类问题。
P类问题就是所有复杂度为多项式时间的问题的集合。
通俗地称所有复杂度为多项式时间的问题为易解的问题类，否则为难解的问题。
有些问题很难找到多项式时间的算法（或许根本不存在），例如“找出无向图中哈米尔顿回路”问题。
但如果给了该问题的一个答案，可以在多项式时间内判断这个答案是否正确。
第1.1章算法复杂性问题-----NP完全问题§1 NP问题与NP完全问题在第一章中我们初步讨论了算法复杂性的概念。
从第三章到第七章，我们讨论了不少问题和它们的算法。
这些问题基本上都是P问题，即它们都有多项式算法。
但在第一章中我们就已经指出，有不少问题至今没有找到多项式算法。
一个问题很自然地摆到我们面前：一个组合最优化问题，如果没有找到它的多项式算法，原因究竟是什么？是因为它本质上就不存在多项式算法呢？还是由于我们研究得不透彻或者我们的能力不够？后一种可能性是可能存在的。
线性规划问题，从三十年代开始提出，一直延续到七十年代，几十年没有找到一个多项式算法，已经有不少人认为线性规划可能没有多项式算法。
但在1979年，年轻的苏联数学工作者XиЧиЯН找到了第一个解线性规划的多项式算法——椭球算法，以后又出现了Karmaka算法。
在科学史上，经过几百年甚至上千年才被攻克的难题不胜枚举。
因此，如果能够根据问题的难度对问题进行分类，将会给算法研究带来巨大的好处。
首先，我们知道我们研究的问题难度很大，不可能找到或者很难找到有效算法，我们将会把精力集中于寻找问题的近似算法，避免了可能无效的研究。
第二，如果我们知道两个问题有相同的难度，那末它们之间必然存在某种内在联系，解决第一问题的方法经过适当的修改很可能就能解决第二个问题，这就对我们寻找一个解决第二个问题的方法带来帮助。
但是，对问题进行分类和判定一个问题属于哪一类，这两件工作都十分困难。
两个看上去很相似的问题，例如第一章中介绍的中国邮递员问题和旅行售货员问题。
但前者提出不久就被判定为P问题，而对后者研究了四十多年却没有结果。
在第一章中我们提到“理想计算机”模式。
目前绝大多数算法理论讨论都在一种“图灵机”的理想数学模型上进行，“图灵机”是为纪念英国科学家图灵而得名，因为他最早提出了这个模型。
图灵机是对目前使用的实际计算机的一个很好的简化和抽象。
凡是用图灵机描述的用多项式时间运行的算法，都可以在实际计算机上用多项式时间运行；反过来，实际计算机上的多项式算法，也都可在图灵机上被描述并按多项式时间运行。
