Oded Goldreich Weizmann Institute of

Science,Israel

Computational Complexity

2008, 606pp.

Hardcover

ISBN 9780521884730

O.哥爾德萊赫著

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

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

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

朱堯辰,研究員

(中國(guó)科學(xué)院應(yīng)用數(shù)學(xué)研究所)

Zhu Yaochen, Professor

(Institute of Applied Mathematics,CAS)