计算复杂性（英文版）
点此进入淘宝搜索页搜索分類: 图书,计算机/网络,计算机理论,
作者： （以）戈德赖希著
出 版 社： 人民邮电出版社
出版时间： 2010-4-1字数： 754000版次： 1页数： 603印刷时间： 2010-4-1开本： 16开印次： 1纸张： 胶版纸I S B N ： 9787115224002包装： 平装
复杂性理论是计算机科学的理论基础的核心。本书是著名计算机科学家Oded Goldreich的力作，书中对计算任务固有复杂性研究进行了概念性介绍，全面分析了复杂性理论的现代主题。
本书涉及复杂性理论的很多子领域（如难度放大、伪随机性及概率证明系统等），涵盖了NP完整性、空间复杂性、随机性和计数、伪随机数生成器等内容，还在附录里面介绍了现代密码学基础等。
本书内容严谨，可读性强，适合作为高年级本科生、研究生的教材。同时，书中展示了复杂性理论的很多子领域，也适合领域专家参考。
Oded Goldreich 以色列魏茨曼科学研究院（Weizmann Institute of Science）计算机科学教授，Meyer W. Weisgal讲席教授。他是SIAM Journal on Computing、Journal of Cryptology和Computational Complexity杂志的特约编辑。
1Introduction and Preliminaries1
1.1Introduction1
1.1.1A Brief Overview of Complexity Theory2
1.1.2Characteristics of Complexity Theory6
1.1.3Contents of This Book8
1.1.4Approach and Style of This Book12
1.1.5Standard Notations and Other Conventions16
1.2Computational Tasks and Models17
1.2.1Representation18
1.2.2Computational Tasks18
1.2.3Uniform Models (Algorithms)20
1.2.4Non-uniform Models (Circuits and Advice)36
1.2.5Complexity Classes42
Chapter Notes43
2P, NP, and NP-Completeness44
2.1The P Versus NP Question46
2.1.1The Search Version: Finding Versus Checking47
2.1.2The Decision Version: Proving Versus Verifying50
2.1.3Equivalence of the Two Formulations54
2.1.4Two Technical Comments Regarding NP55
2.1.5The Traditional Definition of NP55
2.1.6In Support of P Different from NP57
2.1.7Philosophical Meditations58
2.2Polynomial-Time Reductions58
2.2.1The General Notion of a Reduction59
2.2.2Reducing Optimization Problems to Search Problems61
2.2.3Self-Reducibility of Search Problems63
2.2.4Digest and General Perspective67
2.3NP-Completeness67
2.3.1Definitions68
2.3.2The Existence of NP-Complete Problems69
2.3.3Some Natural NP-Complete Problems71
2.3.4NP Sets That Are Neither in P nor NP-Complete81
2.3.5Reflections on Complete Problems85
2.4Three Relatively Advanced Topics87
2.4.1Promise Problems87
2.4.2Optimal Search Algorithms for NP92
2.4.3The Class coNP and Its Intersection with NP94
Chapter Notes97
Exercises99
3Variations on P and NP108
3.1Non-uniform Polynomial Time (P/poly)108
3.1.1Boolean Circuits109
3.1.2Machines That Take Advice111
3.2The Polynomial-Time Hierarchy (PH)113
3.2.1Alternation of Quantifiers114
3.2.2Non-deterministic Oracle Machines 117
3.2.3The P/poly Versus NP Question and PH119
Chapter Notes121
Exercises122
4More Resources, More Power127
4.1Non-uniform Complexity Hierarchies128
4.2Time Hierarchies and Gaps129
4.2.1Time Hierarchies129
4.2.2Time Gaps and Speedup136
4.3Space Hierarchies and Gaps139
Chapter Notes139
Exercises140
5Space Complexity143
5.1General Preliminaries and Issues144
5.1.1Important Conventions144
5.1.2On the Minimal Amount of Useful Computation Space145
5.1.3Time Versus Space146
5.1.4Circuit Evaluation153
5.2Logarithmic Space153
5.2.1The Class L154
5.2.2Log-Space Reductions154
5.2.3Log-Space Uniformity and Stronger Notions155
5.2.4Undirected Connectivity155
5.3Non-deterministic Space Complexity162
5.3.1Two Models162
5.3.2NL and Directed Connectivity164
5.3.3A Retrospective Discussion171
5.4PSPACE and Games172
Chapter Notes175
Exercises175
6Randomness and Counting184
7The Bright Side of Hardness241
8Pseudorandom Generators284
9Probabilistic Proof Systems349
10Relaxing the Requirements416
Epilogue461
Appendix A: Glossary of Complexity Classes463
Appendix B: On the Quest for Lower Bounds469
Appendix C: On the Foundations of Modern Cryptography482
Appendix D: Probabilistic Preliminaries and Advanced Topics inRandomization523
Appendix E: Explicit Constructions545
Appendix F: Some Omitted Proofs566
Appendix G: Some Computational Problems583
Bibliography589
Index60
