计算复杂性概观

Oded Goldreich Weizmann Institute of

Science,Israel

Computational Complexity

2008, 606pp.

Hardcover

ISBN 9780521884730

O.哥尔德莱赫著

复杂性理论是计算机科学的理论基础的一个重要方面,它与计算任务的固有复杂性的一般性研究紧密相关。本书是一本专著,以大学高年级学生和研究生为主要对象,使他们对复杂性理论的概念有一个完整深入的理解,同时也涉及理论的一些其他方面,以兼顾不同专业科技人员的需要。本书作者长期从事复杂性理论和密码学的研究和教学,是该领域国际知名学者。

全书包含10章和7个附录。1.引论和预备,给出复杂性理论的现代观点和一些评论,论述了理论的特征,并提供重要的背景材料;2.论述PMNP问题和NP完全性理论,还讨论了多项式时间归约的概念、NP问题的存在性,以及最优搜索算法、约定问题等;3.考虑了复杂性类P和NP的一些变体(推广),包括非一致多项式时间概念的两种表述,以及多项式时间层次(PH);4.可以看作前章的补充材料,讨论了非一致复杂性层次,证明了时间层次定理;5.研究计算的空间复杂性,着重讨论两种比较极端的情形,即算法分别具有对数空间复杂性及多项式空间复杂性的情形;6.讲述概率性多项式时间算法,讨论了复杂性类BPP,RP及ZPP等,还讨论了与计数有关的复杂性问题;7.研究与P≠NP有关的两个猜想。最后3章是较专门的论题,包括伪随机数生成器、随机性证明系统及计算问题的松弛等。附录是正文的补充,如下界估计、现代密码学、重要的计算问题等。

本书叙述自成一体,证明详细,例子习题较多,比较适宜自学,是有关专业研究生合适的教材,也可供科研人员参考。

朱尧辰,研究员

(中国科学院应用数学研究所)

Zhu Yaochen, Professor

(Institute of Applied Mathematics,CAS)