Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 计算复杂性
发信站: 哈工大紫丁香 (2001年06月03日08:29:32 星期天), 站内信件

计算复杂性
所谓"计算复杂性"，通俗说来，就是用计 算机求解问题的难易程度。其度量标准：一是
计算所需的步数或 指令条数(这叫时间复杂度)，二是计算所需的存储单元数量(这叫 空
间复杂度)。我们当然不可能也不必要就一个个具体问题去研 究它的计算复杂性，而是
依据难度去研究各种计算问题之间的 联系，按复杂性把问题分成不同的类，即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年间就
 发表过一些关于"计算复杂性方面的论文和报告，可惜流传的面 太小，影响不大。但M
IT"慧眼识英雄"，邀情拉宾前来讲学。布卢姆 当时正苦于没有适当的课题作博士论文，
听了拉宾的讲座极感 兴趣，当即决定沿此方向进行研究，其结果就是完成了上述博士
论文。布卢姆的论文不但提出了有关计算复杂性的一些公理，而 且在对复杂性类的归纳
上也比其他学者有更高的抽象度。因此 学术界公认，布、哈、斯三人是计算复杂性理论
的主要奠基人。

--

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

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