Algorithm 版 (精华区)
发信人: Lerry (坐壮:望苗:思汉@贵族 与猫族斗争到底), 信区: Algorithm
标 题: ['95]Manuel Blum
发信站: 哈工大紫丁香 (2002年04月26日07:54:01 星期五), 站内信件
[1995]布卢姆--为计算复杂性理论奠基 (吴鹤龄)
(Ref: http://it.sohu.com/itpeople/Blum.html
http://www.acm.org/awards/turing_citations/blum.html)
=============================================================================
1995年度的图灵奖授予了加州大学伯克利分校著名的计算机科 学家曼纽尔·布卢
姆(Manuel Blum)。布卢姆是计算复杂性理论的奠 基人之一，而计算复杂性是计
算机科学的一个基础性分支，十分 重要。图灵奖至今的39位得主中有6位是由于
在计算复杂性方面 的杰出贡献而获此殊荣。
所谓"计算复杂性"，通俗说来，就是用计 算机求解问题的难易程度其度量标准
：一是计算所需的步数或 指令条数(这叫时间复杂度)，二是计算所需的存储单元
数量(这叫 空间复杂度)。我们当然不可能也不必要就一个个具体问题去研 究它
的计算复杂性，而是依据难度去研究各种计算问题之间的 联系，按复杂性把问题
分成不同的类，即ComplexityClass。
在采用图灵于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"(递归序列的计算复杂
性)，论 文中首次使用了"计算复杂性"这一术语，由此开辟了计算机科学 中的一
个新领域，并为之奠定了理论基础。他们两人是1993年度 图灵奖获得者(以后在
本栏中还将专门介绍)。另一个中心是麻省 理工学院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月号上的论文"Designing Prognams that check
Their Work"。
布卢姆现在在加州大学伯克利分校任教。
=============================================================================
Manuel Blum
Citation
In recognition of his contributions to the foundations of
computational complexity theory and its application to
cryptography and program checking.
=============================================================================
--
--
当一个女孩儿觉得她不太容易了解那个男人的时候，她会爱他。
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 218.7.32.75]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：2.555毫秒