计算机能做什么与不能做什么.pdf

计算机能做什么与不能做什么

计算机是二十世纪人类最伟大的发明，它极大地推动了科学技术

的进步，强烈地影响着人类社会生活的各个方面，并且对人类精神与

智力的至尊地位提出了巨大的挑战。近年来，计算机“深蓝”战胜了国

际象棋天才霸主卡斯帕罗夫，三、四十年前人工智能前辈们的预言终

于成为现实，从任何意义上将这都是极具震撼力的事件。这既是人类

的胜利，也是计算机的胜利。

计算机之所以有力量，硬件的高速发展是一个重要原因，但还不

是最主要的原因。计算机的力量主要来自其软件，软件的核心是算法。

算法是计算机的灵魂，算法的改进所产生的作用要比单纯提高硬件速

度有效得多。算法的历史比计算机长得多，例如求两个整数的最大公

约数的欧几里德算法距今已有两千多年的历史了。算法的理论也极为

深奥，它不仅已是数学的一部分，而且有些内容可以说是元数学的一

部分，例如交互式证明理论。因此，算法的研究一直是计算机研究与

应用中最具挑战性的工作。

计算机算法的研究有两条截然不同的路线：一条路线研究计算机

不能做什么，另一条路线研究计算机能做什么。

研究计算机不能做什么早在计算机诞生之前就已经开始并有了

明确的结论。1936年，图林(Turing)提出了图林机模型，用这个抽象

的计算机模型定义了算法、计算、可计算等概念，证明了存在计算机

不可计算的问题，从而给出了计算机能力的界限。

70年代初期，Cook、Karp定义了NP完全的复杂性类，证明了

相当多的现实问题是NP完全问题。NP完全问题用现有的算法求解

均需要指数长的时间，因此，在现有计算资源下实际上不大可能求解。

这是人类对计算机能力的局限性又一次深刻的揭示。由此诞生的计算

复杂性理论成为理论计算机科学的中心内容。

计算复杂性既是对计算机能力的一大限制，又是对人类认识能力

的一大限制。今天，计算机已成为人类认识自然、改造自然必不可少

的最有力的武器，因此，计算机不能做什么就意味着许多事人类同样

也不能办到。

研究连续问题计算复杂性的著名学者Traub认为，或许有可能从

形式上证明某些科学问题是无法解答的，因为宇宙中不存在能够解答

这类问题的计算资源(时间，存储器，能量等)。

计算复杂性理论也使我们对什么是数学中的美有了新的认识。例

如，图论中一个著名定理是平面图判定的Kuratowski定理，这个定

理说一个图可平面化当且仅当图中不含两种类型的子图。从数学上

讲，这是个优美的定理。但是，直接按这个定理设计计算机程序即算

法，复杂度极高！真正有效的计算机算法选择的完全是另外一条路，

其中主要是深度优先搜索。

这从数学上看似乎不太优美，但是此算法的复杂度是线性的，因

而是极其有效的。因此我们说，计算复杂性使我们对美与效率有了新

的认识，没有效率的美至少是不完美的。

但是，以NP完全性理论为代表的计算复杂性理论也逐渐暴露出

它的局限性。NP完全性理论指出，NP完全问题的求解可能存在本

质困难。但是，NP完全问题在科学研究和生产实践中广泛存在，而

且迫切需要解决。无论多么困难，这些问题是不会消失的。因此，仅

仅指出问题的难解性是不够的，更重要的是给出求解方法。而NP完

全性理论最大的不足就是它不提供正面的解决方法。NP完全性理论

的所有结论基本上是否定性的，非常容易使人在面对真实问题时持一

种悲观、消极的态度。

NP完全性理论的第二个缺陷是它仅指出用一个算法求解一个问

题的所有实例时在最坏情况下可能是指数复杂度的，而我们在真实世

界遇到的问题并不一定正好是最坏实例。即使对每一个算法均存在最

坏实例，也并不意味着某一个实例对所有算法均是最坏的。换句话说，

NP完全性理论只是指出以不变的算法对付万变的问题是存在困难

的，而以万变的算法对付万变的问题则就不受NP完全性理论的限制

了！

可见，NP完全性理论给我们带来对计算