VIP会员
内容简介
复杂性理论是计算机科学的理论基础的核心。本书是计算机科学家Oded Goldreich的力作，书中对计算任务固有复杂性研究进行了概念性介绍，全面分析了复杂性理论的现代主题。
本书涉及复杂性理论的很多子领域（如难度放大、伪*性及概率证明系统等），涵盖了NP完整性、空间复杂性、*性和计数、伪*数生成器等内容，还在附录里面介绍了现代密码学基础等。
本书内容严谨，可读性强，适合作为本科生、研究生的教材。同时，书中展示了复杂性理论的很多子领域，也适合领域专家参考。
目录
1 Introduction and Preliminaries 1
1.1 Introduction 1
1.1.1 A Brief Overview of Complexity Theory 2
1.1.2 Characteristics of Complexity Theory 6
1.1.3 Contents of This Book 8
1.1.4 Approach and Style of This Book 12
1.1.5 Standard Notations and Other Conventions 16
1.2 Computational Tasks and Models 17
1.2.1 Representation 18
1.2.2 Computational Tasks 18
1.2.3 Uniform Models (Algorithms) 20
1.2.4 Non-uniform Models (Circuits and Advice) 36
1.2.5 Complexity Classes 42
Chapter Notes 43
2 P, NP, and NP-Completeness 44
2.1 The P Versus NP Question 46
2.1.1 The Search Version: Finding Versus Checking 47
2.1.2 The Decision Version: Proving Versus Verifying 50
2.1.3 Equivalence of the Two Formulations 54
2.1.4 Two Technical Comments Regarding NP 55
2.1.5 The Traditional Definition of NP 55
2.1.6 In Support of P Different from NP 57
2.1.7 Philosophical Meditations 58
2.2 Polynomial-Time Reductions 58
2.2.1 The General Notion of a Reduction 59
2.2.2 Reducing Optimization Problems to Search Problems 61
2.2.3 Self-Reducibility of Search Problems 63
2.2.4 Digest and General Perspective 67
2.3 NP-Completeness 67
2.3.1 Definitions 68
2.3.2 The Existence of NP-Complete Problems 69
2.3.3 Some Natural NP-Complete Problems 71
2.3.4 NP Sets That Are Neither in P nor NP-Complete 81
2.3.5 Reflections on Complete Problems 85
2.4 Three Relatively Advanced Topics 87
2.4.1 Promise Problems 87
2.4.2 Optimal Search Algorithms for NP 92
2.4.3 The Class coNP and Its Intersection with NP 94
Chapter Notes 97
Exercises 99
3 Variations on P and NP 108
3.1 Non-uniform Polynomial Time (P/poly) 108
3.1.1 Boolean Circuits 109
3.1.2 Machines That Take Advice 111
3.2 The Polynomial-Time Hierarchy (PH) 113
3.2.1 Alternation of Quantifiers 114
3.2.2 Non-deterministic Oracle Machines 117
3.2.3 The P/poly Versus NP Question and PH 119
Chapter Notes 121
Exercises 122
4 More Resources, More Power 127
4.1 Non-uniform Complexity Hierarchies 128
4.2 Time Hierarchies and Gaps 129
4.2.1 Time Hierarchies 129
4.2.2 Time Gaps and Speedup 136
4.3 Space Hierarchies and Gaps 139
Chapter Notes 139
Exercises 140
5 Space Complexity 143
5.1 General Preliminaries and Issues 144
5.1.1 important Conventions 144
5.1.2 On the Minimal Amount of Useful Computation Space 145
5.1.3 Time Versus Space 146
5.1.4 Circuit evaluation 153
5.2 Logarithmic Space 153
5.2.1 The Class L 154
5.2.2 Log-Space Reductions 154
5.2.3 Log-Space Un