计算复杂性 英文2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

计算复杂性 英文PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

1 Introduction and Preliminaries1

1.1 Introduction1

1.1.1 A Brief Overview of Complexity Theory2

1.1.2 Characteristics of Complexity Theory6

1.1.3 Contents of This Book8

1.1.4 Approach and Style of This Book12

1.1.5 Standard Notations and Other Conventions16

1.2 Computational Tasks and Models17

1.2.1 Representation18

1.2.2 Computational Tasks18

1.2.3 Uniform Models(Algorithms)20

1.2.4 Non-uniform Models(Circuits and Advice)36

1.2.5 Complexity Classes42

Chapter Notes43

2 P,NP,and NP-Completeness44

2.1 The P Versus NP Question46

2.1.1 The Search Version:Finding Versus Checking47

2.1.2 The Decision Version:Proving Versus Verifying50

2.1.3 Equivalence of the Two Formulations54

2.1.4 Two Technical Comments Regarding NP55

2.1.5 The Traditional Definition of NP55

2.1.6 In Support of P Different from NP57

2.1.7 Philosophical Meditations58

2.2 Polynomial-Time Reductions58

2.2.1 The General Notion of a Reduction59

2.2.2 Reducing Optimization Problems to Search Problems61

2.2.3 Self-Reducibility of Search Problems63

2.2.4 Digest and General Perspective67

2.3 NP-Completeness67

2.3.1 Definitions68

2.3.2 The Existence of NP-Complete Problems69

2.3.3 Some Natural NP-Complete Problems71

2.3.4 NP Sets That Are Neither in P nor NP-Complete81

2.3.5 Reflections on Complete Problems85

2.4 Three Relatively Advanced Topics87

2.4.1 Promise Problems87

2.4.2 Optimal Search Algorithms for NP92

2.4.3 The Class coNP and Its Intersection with NP94

Chapter Notes97

Exercises99

3 Variations on P and NP108

3.1 Non-uniform Polynomial Time (P/poly)108

3.1.1 Boolean Circuits109

3.1.2 Machines That Take Advice111

3.2 The Polynomial-Time Hierarchy(PH)113

3.2.1 Alternation of Quantifiers114

3.2.2 Non-deterministic Oracle Machines117

3.2.3 The P/poly Versus NP Question and PH119

Chapter Notes121

Exercises122

4 More Resources,More Power?127

4.1 Non-uniform Complexity Hierarchies128

4.2 Time Hierarchies and Gaps129

4.2.1 Time Hierarchies129

4.2.2 Time Gaps and Speedup136

4.3 Space Hierarchies and Gaps139

Chapter Notes139

Exercises140

5 Space Complexity143

5.1 General Preliminaries and Issues144

5.1.1 Important Conventions144

5.1.2 On the Minimal Amount of Useful Computation Space145

5.1.3 Time Versus Space146

5.1.4 Circuit Evaluation153

5.2 Logarithmic Space153

5.2.1 The Class L154

5.2.2 Log-Space Reductions154

5.2.3 Log-Space Uniformity and Stronger Notions155

5.2.4 Undirected Connectivity155

5.3 Non-deterministic Space Complexity162

5.3 Two Models162

5.3.2 NL and Directed Connectivity164

5.3.3 A Retrospective Discussion171

5.4 PSPACE and Games172

Chapter Notes175

Exercises175

6 Randomness and Counting184

6.1 Probabilistic Polynomial Time185

6.1.1 Basic Modeling Issues186

6.1.2 Two-Sided Error:The Complexity Class BPP189

6.1.3 One-Sided Error:The Complexity Classes RP and coRP193

6.1.4 Zero-Sided Error:The Complexity Class ZPP199

6.1.5 Randomized Log-Space199

6.2 Counting202

6.2.1 Exact Counting202

6.2.2 Approximate Counting211

6.2.3 Searching for Unique Solutions217

6.2.4 Uniform Generation of Solutions220

Chapter Notes227

Exercises230

7 The Bright Side of Hardness241

7.1 One-Way Functions242

7.1.1 Generating Hard Instances and One-Way Functions243

7.1.2 Amplification of Weak One-Way Functions245

7.1.3 Hard-Core Predicates250

7.1.4 Reflections on Hardness Amplification255

7.2 Hard Problems in E255

7.2.1 Amplification with Respect to Polynomial-Size Circuits257

7.2.2 Amplification with Respect to Exponential-Size Circuits270

Chapter Notes277

Exercises278

8 Pseudorandom Generators284

Introduction285

8.1 The General Paradigm288

8.2 General-Purpose Pseudorandom Generators290

8.2.1 The Basic Definition291

8.2.2 The Archetypical Application292

8.2.3 Computational Indistinguishability295

8.2.4 Amplifying the Stretch Function299

8.2.5 Constructions301

8.2.6 Non-uniformly Strong Pseudorandom Generators304

8.2.7 Stronger Notions and Conceptual Reflections305

8.3 Derandomization of Time-Complexity Classes307

8.3.1 Defining Canonical Derandomizers308

8.3.2 Constructing Canonical Derandomizers310

8.3.3 Technical Variations and Conceptual Reflections313

8.4 Space-Bounded Distinguishers315

8.4.1 Definitional Issues316

8.4.2 Two Constructions318

8.5 Special-Purpose Generators325

8.5.1 Pairwise Independence Generators326

8.5.2 Small-Bias Generators329

8.5.3 Random Walks on Expanders332

Chapter Notes334

Exercises337

9 Probabilistic Proof Systems349

Introduction and Preliminaries350

9.1 Interactive Proof Systems352

9.1.1 Motivation and Perspective352

9.1.2 Definition354

9.1.3 The Power of Interactive Proofs357

9.1.4 Variants and Finer Structure:An Overview363

9.1.5 On Computationally Bounded Provers:An Overview366

9.2 Zero-Knowledge Proof Systems368

9.2.1 Definitional Issues369

9.2.2 The Power of Zero-Knowledge372

9.2.3 Proofs of Knowledge-A Parenthetical Subsection378

9.3 Probabilistically Checkable Proof Systems380

9.3.1 Definition381

9.3.2 The Power of Probabilistically Checkable Proofs383

9.3.3 PCP and Approximation398

9.3.4 More on PCP Itself:An Overview401

Chapter Notes404

Exercises406

10 Relaxing the Requirements416

10.1 Approximation417

10.1.1 Search or Optimization418

10.1.2 Decision or Property Testing423

10.2 Average-Case Complexity428

10.2.1 The Basic Theory430

10.2.2 Ramifications442

Chapter Notes451

Exercises453

Epilogue461

Appendix A:Glossary of Complexity Classes463

A.1 Preliminaries463

A.2 Algorithm-Based Classes464

A.2.1 Time Complexity Classes464

A.2.2 Space Complexity Classes467

A.3 Circuit-Based Classes467

Appendix B:On the Quest for Lower Bounds469

B.1 Preliminaries469

B.2 Boolean Circuit Complexity471

B.2.1 Basic Results and Questions472

B.2.2 Monotone Circuits473

B.2.3 Bounded-Depth Circuits473

B.2.4 Formula Size474

B.3 Arithmetic Circuits475

B.3.1 Univariate Polynomials476

B.3.2 Multivariate Polynomials476

B.4 Proof Complexity478

B.4.1 Logical Proof Systems480

B.4.2 Algebraic Proof Systems480

B.4.3 Geometric Proof Systems481

Appendix C:On the Foundations of Modern Cryptography482

C.1 Introduction and Preliminaries482

C.1.1 The Underlying Principles483

C.1.2 The Computational Model485

C.1.3 Organization and Beyond486

C.2 Computational Difficulty487

C.2.1 One-Way Functions487

C.2.2 Hard-Core Predicates489

C.3 Pseudorandomness490

C.3.1 Computational Indistinguishability490

C.3.2 Pseudorandom Generators491

C.3.3 Pseudorandom Functions492

C.4 Zero-Knowledge494

C.4.1 The Simulation Paradigm494

C.4.2 The Actual Definition494

C.4.3 A General Result and a Generic Application495

C.4.4 Definitional Variations and Related Notions497

C.5 Encryption Schemes500

C.5.1 Definitions502

C.5.2 Constructions504

C.5.3 Beyond Eavesdropping Security505

C.6 Signatures and Message Authentication507

C.6.1 Definitions508

C.6.2 Constructions509

C.7 General Cryptographic Protocols511

C.7.1 The Definitional Approach and Some Models512

C.7.2 Some Known Results517

C.7.3 Construction Paradigms and Two Simple Protocols517

C.7.4 Concluding Remarks522

Appendix D:Probabilistic Preliminaries and Advanced Topics in Randomization523

D.1 Probabilistic Preliminaries523

D.1.1 Notational Conventions523

D.1.2 Three Inequalities524

D.2 Hashing528

D.2.1 Definitions528

D.2.2 Constructions529

D.2.3 The Leftover Hash Lemma529

D.3 Sampling533

D.3.1 Formal Setting533

D.3.2 Known Results534

D.3.3 Hitters535

D.4 Randomness Extractors536

D.4.1 Definitions and Various Perspectives537

D.4.2 Constructions541

Appendix E:Explicit Constructions545

E.1 Error-Correcting Codes546

E.1.1 Basic Notions546

E.1.2 A Few Popular Codes547

E.1.3 Two Additional Computational Problems551

E.1.4 A List-Decoding Bound553

E.2 Expander Graphs554

E.2.1 Definitions and Properties555

E.2.2 Constructions561

Appendix F:Some Omitted Proofs566

F.1 Proving That PH Reduces to #P566

F.2 Proving That IP(f)？AM(O(f))？AM(f)572

F.2.1 Emulating General Interactive Proofs by AM-Games572

F.2.2 Linear Speedup for AM578

Appendix G:Some Computational Problems583

G.1 Graphs583

G.2 Boolean Formulae585

G.3 Finite Fields,Polynomials,and Vector Spaces586

G.4 The Determinant and the Permanent587

G.5 Primes and Composite Numbers587

Bibliography589

Index601