計算復雜性概觀

Oded Goldreich Weizmann Institute of

Science,Israel

Computational Complexity

2008, 606pp.

Hardcover

ISBN 9780521884730

O.哥爾德萊赫著

復雜性理論是計算機科學的理論基礎的一個重要方面,它與計算任務的固有復雜性的一般性研究緊密相關。本書是一本專著,以大學高年級學生和研究生為主要對象,使他們對復雜性理論的概念有一個完整深入的理解,同時也涉及理論的一些其他方面,以兼顧不同專業(yè)科技人員的需要。本書作者長期從事復雜性理論和密碼學的研究和教學,是該領域國際知名學者。

全書包含10章和7個附錄。1.引論和預備,給出復雜性理論的現代觀點和一些評論,論述了理論的特征,并提供重要的背景材料;2.論述PMNP問題和NP完全性理論,還討論了多項式時間歸約的概念、NP問題的存在性,以及最優(yōu)搜索算法、約定問題等;3.考慮了復雜性類P和NP的一些變體(推廣),包括非一致多項式時間概念的兩種表述,以及多項式時間層次(PH);4.可以看作前章的補充材料,討論了非一致復雜性層次,證明了時間層次定理;5.研究計算的空間復雜性,著重討論兩種比較極端的情形,即算法分別具有對數空間復雜性及多項式空間復雜性的情形;6.講述概率性多項式時間算法,討論了復雜性類BPP,RP及ZPP等,還討論了與計數有關的復雜性問題;7.研究與P≠NP有關的兩個猜想。最后3章是較專門的論題,包括偽隨機數生成器、隨機性證明系統(tǒng)及計算問題的松弛等。附錄是正文的補充,如下界估計、現代密碼學、重要的計算問題等。

本書敘述自成一體,證明詳細,例子習題較多,比較適宜自學,是有關專業(yè)研究生合適的教材,也可供科研人員參考。

朱堯辰,研究員

(中國科學院應用數學研究所)

Zhu Yaochen, Professor

(Institute of Applied Mathematics,CAS)