計算複雜性

複雜性理論是計算機科學的理論基礎的核心。本書是著名計算機科學家Oded Goldreich的力作，書中對計算任務固有複雜性研究進行了概念性介紹，全面分析了複雜性理論的現代主題。

本書涉及複雜性理論的很多子領域（如難度放大、偽隨機性及概率證明系統等），涵蓋了NP完整性、空間複雜性、隨機性和計數、偽隨機數生成器等內容，還在附錄裡面介紹了現代密碼學基礎等。

本書內容嚴謹，可讀性強，適合作為高年級本科生、研究生的教材。同時，書中展示了複雜性理論的很多子領域，也適合領域專家參考。

Oded Goldreich 以色列魏茨曼科學研究院（Weizmann Institute of Science）計算機科學教授，Meyer W Weisgal講席教授。他是SIAM Journal on Computing、Journal of Cryptology和Computational Complexity雜誌的特約編輯。

1　Introduction and Preliminaries　1

2　P NP and NP-Completeness　44

3　Variations on P and NP　108

4　More Resources,More Power　127

5　Space Complexity　143

6　Randomness and Counting　184

7　The Bright Side of Hardness　241

8　Pseudorandom Generators　284

9　Probabilistic Proof Systems　349

10　Relaxing the Requirements　416

Epilogue　461

Index　60