《計算複雜性》是2010年人民郵電出版社出版社出版的圖書，作者是戈德賴希。
基本介紹
- 書名：計算複雜性
- 作者：戈德賴希
- ISBN：9787115224002
- 頁數：603
- 定價：99.00
- 出版社：人民郵電出版社
- 出版時間：2010-04-01
- 裝幀：平裝
- 開本：16開
- 紙張：膠版紙
- 版次：1
內容簡介,作者簡介,圖書目錄,
內容簡介
複雜性理論是計算機科學的理論基礎的核心。本書是著名計算機科學家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
