计算复杂性

来源:用户上传      作者: S.阿伦拉等

　　纵观历史,人们对在有限的步骤内从一组输入中产生一个输出这一过程具有模糊的概念,他们认为“计算”是一个人遵循某些规则随意进行的过程。20世纪前50年中一个重要的科学进步就是“计算”这个概念获得了更为准确的定义。基于这个定义,计算可能发生在各种物理及数学系统中,这一点很快就变得很明确。图灵机引入演算,细胞自动机、指针机、康威的生命游戏等。令人惊讶的是所有这些计算形式都是等价的,在某种意义上,每一个模型都没有实现我们对任何其他模型所设想的所有计算。德国数学家希尔伯特在1900年指出,只要科学的一个分支能提供充裕的问题,那么它就是有生命力的;缺乏问题则预示着该分支独立发展的灭绝或中断。这正是对计算复杂性的写照。
　　本书描述了计算复杂性理论的最新进展与经典成果。包括了300个练习题及有选择的提示,每章结尾都有对该章内容的注释及其历史的介绍。
　　本书共有24章,分成了基本的复杂性类别,具体计算模型的下界和高级课题三部分。1,符号惯例;2,计算模型及为什么它无关紧要;3,NP及NP的完整性;4,对角线法;5,空间复杂性;6,多项式层级及交替;7,布尔电路;8,随机化计算;9,交互式证明;10,密码学;11,量子计算;12,PCP理论及不可近似性入门;13,决策树;14通讯的复杂性;15,电路的下界;16,复杂性理论的滑铁卢;17,证明的复杂性;18,代数计算模型;19,计数的复杂性,平均复杂性理论:列文理论;20,硬度放大与错误校正;21,去随机化;22,伪随机构造:扩展器与析解器;23,PCP0定理的证明与傅里叶变换技术;24,为何电路下界如此困难。最后是总标题为数学背景的6个附录。
　　两位作者分别是普林斯顿大学计算机科学系教授及助理教授,第一作者也是由美国科学基金会资助的计算难解性中心的创始负责人。关于本书,普林斯顿高等研究所的A.Wigderson写道:“计算复杂性理论是理论计算机科学研究的核心,本书实际上包括了过去20年所有振奋人心的发展,还有高层次的直觉及详尽的技术证明”。MIT数学系主任M.Sipse写道:“本书是一个主要的成就,汇总了复杂性理论中所有重要的进展,……”。本书可用作对复杂性感兴趣的包括物理学家、数学家及其他科学家的参考资料。
　　胡光华,高级软件工程师

转载注明来源:https://www.xzbu.com/8/view-1061492.htm