Algorithm 版 (精华区)

发信人: ssos (存在与虚无·戒酒戒网), 信区: Algorithm
标  题: 布卢姆--为计算复杂性理论奠基 　　
发信站: 哈工大紫丁香 (2001年08月23日17:12:35 星期四), 站内信件

1995年度的图灵奖授予了加州大学伯克利分校著名的计算机科 学家曼纽尔·布卢姆(Ma
nuel Blum)。布卢姆是计算复杂性理论的奠 基人之一，而计算复杂性是计算机科学的一
个基础性分支，十分 重要。图灵奖至今的39位得主中有6位是由于在计算复杂性方面 的
杰出贡献而获此殊荣。
所谓"计算复杂性"，通俗说来，就是用计 算机求解问题的难易程度。其度量标准：一是
计算所需的步数或 指令条数(这叫时间复杂度)，二是计算所需的存储单元数量(这叫 空
间复杂度)。我们当然不可能也不必要就一个个具体问题去研 究它的计算复杂性，而是
依据难度去研究各种计算问题之间的 联系，按复杂性把问题分成不同的类，即Complex
ityClass。
在采用图灵于30年代提出的理想化的 计算模型即图灵机作为标准的计算工具的情况下，
可以非形式 化地定义如下几类计算问题：
1。P类问题：由确定型图灵机在多项式时间内可解的一切判 定问题所组成的集合；
2。NP类问题：由非确定型图灵机在多项式时间内可计算的判定 问题所组成的集合；
3。NP完全问题：如果判定问题π∈NP，并且对所有其他判定问题 π∈NP，都有π'多项
式变换到π(记为π'∞π)，则称判定问题π 是NP完全的。
对P类，NP类及NP完全问题的研究推动 了计算复杂性理论的发展，产生了许多新概念，
提出了许多新方 法。但是还有许多难题至今没有解决，P=?NP就是其中之一。许多学 者
猜想P≠NP，但无法证明。
计算复杂性的研究始于50年代末、60年 代初，当时在美国有两个并行的中心，一个是通
用电气公司设立 于纽约州斯克内克塔迪(Schenectady)的研究实验室，核心人物是哈 特
马尼斯(J.Hartmanis)和斯提恩斯(R.Stearns)。1964年11月，他们在普林斯 顿举行的第
五届开关电路理论和逻辑设计学术年会上发表了论 文"Computational Complexity of 
recursivese quences"(递归序列的计算复杂性)，论 文中首次使用了"计算复杂性"这一
术语，由此开辟了计算机科学 中的一个新领域，并为之奠定了理论基础。他们两人是1
993年度 图灵奖获得者(以后在本栏中还将专门介绍)。另一个中心是麻省 理工学院MIT
，在那里，布卢姆与前述两人互相独立地进行着相关 问题的研究，并完成了他的博士论
文："Amachine independent theory of the complexity of recursive functions"(递
归函数复杂性的机器独立理论)，该论 文的详细摘要1967年发表于《J.ACM》14(2)P322
～336。实际上，布卢姆 是受以色列学者拉宾(M.O.Rabin)的启发而开始这方面的研究的
。拉 宾是希伯莱大学的教授，是研究计算复杂性问题的先驱，并在 1976年荣获图灵奖
(以后也将专门介绍)。拉宾在1959～1960年间就 发表过一些关于"计算复杂性方面的论
文和报告，可惜流传的面 太小，影响不大。但MIT"慧眼识英雄"，邀情拉宾前来讲学。
布卢姆 当时正苦于没有适当的课题作博士论文，听了拉宾的讲座极感 兴趣，当即决定
沿此方向进行研究，其结果就是完成了上述博士 论文。布卢姆的论文不但提出了有关计
算复杂性的一些公理，而 且在对复杂性类的归纳上也比其他学者有更高的抽象度。因此
 学术界公认，布、哈、斯三人是计算复杂性理论的主要奠基人。
布卢姆除了在计算复杂性理论方面做 出了开创性贡献以外，还致力于将这一理论应用于
对计算机系 统的安全性和通信的安全性有十分重要意义的"密码学"以及在" 软件工程"
中十分重要而又十分困难的程序正确性验证方面，并 且取得了令人瞩目的成就。1989年
5月，他和同事Sampath Kannan在西 雅图召开的21届ACM计算理论专题研讨会上所提交的
一篇论文 中，首次提出了"Program Checker"的概念，并综合利用密码学、概率算 法和
程序测试、概率交互证明等手段解决程序正确性验证这一 难题，把这一领域的研究推进
了一大步。有兴趣的读者可参阅他 们发表在《J.ACM》1995年1月号上的论文"Designin
g Prognams that check Their Work"。

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]