CH4计算复杂性-NPppt课件.ppt

可计算性与计算复杂性第四部分2020/9/221并非任何问题都可以利用计算机来解决。可计算理论讨论的是“什么样的问题可以利用计算机来解决,而什么样的则不可。”——可计算(可解、不可解)理论上,一个可计算问题不一定是实际可计算的。在什么情况下认为是满意地解决了?显然这个答案依据于该问题的已知算法的实际效果。如果一个问题有一个算法,其所用时间不是不可允许的(这是应用的主要准则),那么这个问题就认为是解决了,否则就认为是没有解决。虽然理论上是能解决的!即它讨论的是计算的“难”和“易”——能行可计算(难、易)2020/9/222前面我们已经学****了如何度量、分析问题的计算复杂性。那么,如何区分一个问题是“难”还是“易”呢?不同的算法具有很不相同的时间复杂性函数,什么样的算法算作“效率高”,什么样的算法算作“效率低”?Cobham[1964]和Edmonds[1965]首先讨论了这种区别的基本性质。特别是Edmonds把多项式时间算法与“好的”算法等同看待,并且猜想某些整数规划问题可能不能用这种“好的”算法求解。这反映了一种观点,认为指数时间算法不应该算作“好的”算法。2020/9/223目前,计算机科学家们基本上有了一种共识,认为解决一个计算问题的算法,仅当其复杂性随问题规模的增加而多项式的增长时,这个算法才是实际有效的。即将可在多项式时间内解决的问题看作是“易”解决的问题,而将需要指数函数时间解决的问题看作是“难”问题。显然,其渐近复杂性自身不是多项式的,但它有一个多项式的上界,这样的算法也是可接受的。2020/9/;;,但不影响易解问题和难解问题的划分;为什么把多项式时间复杂性作为易解问题和难解问题的分界线?2020/9/225但要注意,多项式算法也要考虑n的幂次,例如,当算法复杂性为O(n80),大概就是不可能接受了,它意味着运算量大致为kn80。解一个规模为n=10的问题时,1080已经是一个天文数字了!因此,多项式算法未必都有效。所以,理论上证明指数型的算法,当然不是有效的。但理论上是多项式的算法,同样实际上不一定可行,它也不是好算法。多项式算法都有效吗?2020/9/226另一方面,有些指数时间算法在实际中可能十分有用。时间复杂性为2n的算法仅仅表示至少有一个规模为n的问题实例需要这么多的运算时间,而大多数问题实例可能实际上需要远比这个少得多的时间。有几个著名的算法就是这种情况。线性规划的单纯形算法具有指数时间复杂性[KleeandMinty,1972],但是在实际中它计算得很好,给人留下了深刻印象。同样,背包问题的分支界限算法虽然也具有指数时间复杂性,但是它是一种非常成功的算法,使得许多人认为背包问题已经很好地解决了。指数型算法都不可行吗?2020/9/227遗憾的是,像这样的例子太少了。虽然对于很多问题都知道指数时间算法,但是只有少数几个被认为在实际中是很有用的。甚至上面提到的那几个成功的指数时间算法也没有使研究人员停止继续寻找这些问题的多项式时间算法的努力。实际上,这些算法的真正成功让人们产生了一种猜疑,认为它们不知怎么地抓住了这些问题的关键性的性质,对这些性质的仔细研究可能给出更好的方法,至今在解释这种成功方面几乎毫无进展,也没有一种方法能够事先预言给定的指数时间算法在实际中能否快速运算。2020/9/228很多问题目前还不能了解其内在的计算复杂性,或者目前还没有找到多项式算法。计算机科学家对这类问题更感兴趣。其中有些是有实际背景的重要问题。问题是否存在多项式算法?如果有的话,人们可以继续探索,如果没有人们也就死心了!于是人们考虑把复杂性大致相同的问题归类研究,得到了一些可喜的成果。经研究发现有一类问题难度相当。它们具有这样的性质:若有一问题找到多项式算法,则它们的全体都得到解决;同样若证明了它们中的任何一个肯定不存在有效算法,对它们全体的努力就可以放弃。2020/9/229这就是著名的NP完备性理论。它不是打算找出这一类问题的算法,仅着眼证明这一类问题的等价性,即证明它们的困难程度相当,若其中一个问题获得多项式解法,则这一类问题全部获得解决。同样若证明它中间的任一问题没有有效算法,则全体都没有。为了客观地、更好地、深入地讨论问题的难易,我们首先了解一下计算模型。2020/9/2210