参考资料NP完全问题-一些重要的概念

《参考资料NP完全问题-一些重要的概念》由会员分享，可在线阅读，更多相关《参考资料NP完全问题-一些重要的概念（19页珍藏版）》请在金锄头文库上搜索。

1、NP完全问题*1一、一些重要的概念 1、多项式时间算法和难解问题不同的算法具有很不相同的时间复杂性函数，什么样的算法算作 “效率高”，什么样的算法算作“效率低”，计算机科学家们公 认一种简单的区别，这就是多顶式时间算法（polynomial time algorithm)和指数时间算法（exponential time algorithm)之间的区别。Cobham1964和Edmonds1965首先 讨论了这种区别的基本性质。特别是Edmonds把多项式时间算法与 “好的”算法等同看待，并且猜想某些整数规划问题可能不能用 这种“好的”算法求解。这反映了一种观点，认为指数时间算法 不应该算作“好

2、的”算法。通常也的确是这样的。大多数指数时 间算法只是穷举搜索法的变种，而多项式时间算法通常只有在对 问题的结构有了某些比较深入的了解之后才有可能给出。艰多人 都认为只有知道了问题的多项式时间算法才能认为“很好地解决 了”这个问题。因此，如果一个问题困难到不可能用多项式时间 算法求解，那末我们就认为这个问题是“难解的”。 Date2不过，有些指数时间算法在实际中可能十分有用。 作为定义，时间复杂性是一种最坏情况的度量。时间复 杂性为2n的算法仅仅表示至少有一个规模为n的问题实 例需要这么多的运算时间，而大多数问题实例可能实际 上需要远比这个少得多的时间。有几个著名的算法就是 这种情况。已经证明

3、线性规划的单纯形算法具有指数时 间复杂性Klee and Minty，1972，但是在实际中它 计算得很好，给人留下了深刻印象。同样，背包问题的 分支界限算法虽然也具有指数时间复杂性，但是它是一 种非常成功的算法，使得许多人认为背包问题已经很好 地解决了。Date3遗憾的是，像这样的例子太少了。虽然对于很多问 题都知道指数时间算法，但是只有少数几个被认为在实 际中是很有用的。甚至上面提到的那几个成功的指数时 间算法也没有使研究人员停止继续寻找这些问题的多项 式时间算法的努力。实际上，这些算法的真正成功产生 了一种猜疑，认为它们不知怎么地抓住了这些问题的关 键性的性质，对这些性质的仔细研究可能给

4、出更好的方 法，至今在解释这种成功方面几乎毫无进展，也没有一 种方法能够事先预言给定的指数时间算法在实际中能否 快速运算。Date4另一方面，如果多项式时间算法满足对运算时 间更严格得多的限制，就往往可以作出这种预言。 虽然可以认为时间复杂性为n100或1099n2的算法在实 际中不大可能快速运算，但是自然提出的多项式可 解的问题大多数可用2次，或者在最坏的情况下用3 次多项式时间算法求解，而且在多项式中不包含特 别大的系数，可以认为满足这些限制的算法是“可 证地有效”算法。正是这种特别需要的性质使我们 优先考虑用多项式时间算法解决问题。Date5关于计算机模型的选择可以作类似的注释。至今 研

5、究过的所有实际的计算机模型，例如单带图灵机， 多带图灵机以及随机存取机（RAM）都是相对于多项式 时间复杂性等价的，人们可以指望任何其它“合理的 ”模型都享有这种等价性。这里所说的“合理的”概 念在本质上是指在单位时间内可以完成的工作量有一 个多项式界限。例如，不能认为具有完成任意多道并 行运算能力的模型是“合理的“，而且也确实不存在 一合计算机具有这种能力。无论如何，只要我们规定 只采用实际的计算机标准模型，难解的问题类就不受 使用的具体模型的影响。因而我们可以根据方便与否 来选择计算机模型，而不会妨碍结果的使用。 “合理 的”计算机模型也称为是“确定型”（ deterministic)的计

6、算机模型。Date6这样一来，“难解的”定义在理论上给出了重要的 一般原则。即问题的难度在本质上不依赖于用来决定时 间复杂性的具体编码方案和计算机模型。能够用实际的计算机标准模型在多项式时间算法（ Polynomial time algorithm)内求解的问题称为P类问 题。Date72、可证的难解问题 最早证出的难解性问题结果是经典的图灵不可判定性 。四十多年前，图灵证明某些问题困难到“不可判定 的”程度，即根本不可能给出解这些问题的算法。例 如，他证明不可能给出一个算法，当任意给定一个计 算机程序和这个程序的输入时，该算法可以判定当把 这个程序应用于这个输入时最终是否停机Turing，

7、1936。现在已经知道还有各种其它问题也是不可判定 的，这些问题包括有限表示群的平凡问题Rabin， 1958，希尔伯特第十问题（整数多项式的可解性） Matijasevic，1970等。因为不可能用任何算法， 当然更不可能用多项式时间算法解这些不可判定问题 ，所以它们的确是在特别强的意义下难解的。Date8第一个难解的“可判定”问题是在六十年代初获 得的，它是Hartmanis和Stearns1965的复杂性“ 谱系”工作的一部分，但是，这些结果只包括一些“ 人工制造的”问题，它们被专门构造成具有所需要的 性质。直到七十年代初，Meyer和Stockmeyer1972 ，Fischer和Ra

8、bin1974以及其他人终于成功地证 明某些“自然的”可判定问题是难解的，这些问题包 括自动机理论、形式语言理论以及数理逻辑中以前研 究过的各种问题。实际上，他们的证明表明甚至用“ 非确定型”（nondeterministic)计算机模型也不可 能在多项式时间内解这些问题，这种“非确定型”计 算机模型具有执行无限多个独立的并行计算序列的能 力。这种“不合理的”计算机模型在NP完全性理论中 起着重要的作用。Date9迄今为止我们已经知道的所有可证的难解问题 分成刚才叙述的两种类型，它们或者是“不可判定的 ”，或者是“非确定型”难解的。但是，大多数在实 际中遇到的在表面上看来难解的问题是可判定的，

9、并 且可以用非确定型计算机在多项式时间内求解。因此 ，要证明这些问题的表面上的难解性，至今所研究过 的证明方法都还不够有力。Date103、NP完全问题 可以用“非确定型”计算机通过多项式时间算法求解 的问题称为“NP类”问题。理论工作者们一方面继续 寻找更有力的方法来证明问题的难解性，同时又在努 力研究就难度而言各种问题相互联系的方式。发现问 题之间的这种相互联系常常可以给算法设计人员提供 有用的信息。证明两个问题相关的基本方法是通过给 出一个构造性变换把第一个问题的任一实例映射到第 二个问题的一个等价的实例，从而把第一个问题“归 约”为第二个问题。这样的变换提供了一个手段，把 解第二个问题

10、的任何算法转变成解第一个问题的相应 的算法。Date11早期就找到了许多这种简单的归约。例如，Dantzig 1960把一些组合最优化问题归约为一般的0-l整数线 性规划问题，Edmonds1962把图论问题“用最少的顶 点覆盖所有边”和“寻找最大的顶点独立集”归约为一 般的“集合覆盖问题”。Gimple1965把一般的集合 覆盖问题归约为逻辑设计的“素蕴涵覆盖问题”， Dantzig，Blattner和Rao1966描述了一个“著名的” 归约，把巡回推销员问题归约为带非负边长的“最短路 径问题”。Date12Stephen Cook于1971年发表的题为“定理证明过程的复杂性 ”一文奠定了N

11、P完全性理论的基础。在这篇简洁而又精致的文章 中Cook做了几件重要的事情。第一，他强调了“多项式时间可归约性”的重要意义，所谓 多项式时间归约是指可以用多项式时间算法实现所需要的变换的 归约。如果我们有从第一个问题到第二个问题的多项式时间归约 ，那末就一定能把第二个问题的任何多项式时间算法转换成第一 个问题的多项式时间算法。第二，他把注意力集中在判定向题的NP类上，这类问题可以 用非确定型计算机在多项式时间内解决。（如果问题的解不是“ 是”就是“否”，则称这个问题是判定向题。）在实际中遇到的 表面上看来难解的问题，当把它们表成判定问题时，大多数属于 这一类。Date13第三，他证明了NP中的

12、一个名叫“可满足性”问题 的具体问题具有这样的性质：NP类中的所有其它问题都 可以多项式归约为这个问题。如果可满足性问题可以用 多项式时间算法解决，那末NP类中的所有问题也都可以 用多项式时间算法解决。如果NP中的某个问题是难解的 ，那末可满足性问题也一定是难解的。因此，在某种意 义下，可满足性问题是NP类中“最难的”问题。最后，Cook认为NP类中的一些其它问题可能和可满 足性问题一样，具有这种成为NP类中“最难的”问题的 性质。他证明对于问题“给定的图G是否包含k个顶点上 的完全子图？其中k 是给定的自然数”就是这种清况。Date14随后，Richard Karp给出了一组结果1972，证

13、 明许多著名的组合问题,包括巡回推销员问题在内的判 定问题形式确实恰好与可满足性问题一样难。从那以后 证明了各种各样的其它问题在难度上等价于这些问题， 这些问题构成了一个NP等价问题(NP equivalent problem)类 ，并给这个等价类起了一个名字，叫做NP 完全问题(NP complete problem)类，它是由NP中所有 “最难的”问题组成。已经证明Cook的原始思想是相当有力的。它提供了 一些方法把许多个别的复杂性问题联合成一个问题：NP 完全问题是难解的吗？由于越来越多的具有独立意义的 问题被证明属于这个等价类，所以它的重要性还在继续 增长。Date15现在认为NP完全

14、问题是否是难解的这一向题是当代 数学和计算机科学中尚未解决的最重要问题之一。尽管 大多数研究工作者猜想NP完全问题是难解的，然而在证 明或否定这个广泛的猜想方面几乎没有取得什么进展。 但是，即使没有证明NP完全性蕴涵难解性，知道一个问 题是NP完全的至少暗示着要想用多项式时间算法解这个 问题必须有重大的突破。Date16实用中，知道一个问题是NP完全的就给我们提供 了有价值的信息，告诉我们采用什么样的途径可以是 最富有成效的。一定不要去优先寻找有效的、精确的 算法。现在比较适当的途径是集中精力致力于其他较 低目标的方法。例如，你可以寻找解决这个问题的各 种特殊情况的有效算法。寻找在大多数情况下看来能 快速运算的算法，虽然不能保证它在任何情况下都能 快速地运算。或者你甚至可以放松问题的某些方面， 寻找一个只能给出满足大部分要求的快速算法。简言 之，NP完全性理论的初步应用是帮助算法设计人员找 到最有可能得到有用的算法的努力方向。Date17总结 问题求解的难度： 不可判定问题 可判定的问题 时间复杂性为多项式的（P） 用不确定型计算机求解时间复杂性为多项式的（NP） NP完全类Date18Date19