Computational Complexity : A Conceptual Perspective

Complexity theory is a central field of the theoretical foundations of computer science. It is concerned with the general study of the intrinsic complexity of computational tasks; that is, it addresses the question of what can be achieved within limited time (and/or with other limited natural computational resources). This book offers a conceptual perspective on complexity theory. It is intended to serve as an introduction for advanced undergraduate and graduate students, either as a textbook or for self-study. The book will also be useful to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems. In each case, the author starts by posing the intuitive questions that are addressed by the sub-area and then discusses the choices made in the actual formulation of these questions, the approaches that lead to the answers, and the ideas that are embedded in these answers. Cover 1 Half-title 3 Title 5 Copyright 6 Dedication 7 Contents 9 List of Figures 15 Preface 17 Organization and Chapter Summaries 19 Acknowledgments 25 Charptr 1 Introduction and Preliminaries 27 1.1 Introduction 27 1.1.1 A Brief Overview of Complexity Theory 28 1.1.2 Characteristics of Complexity Theory 32 1.1.3 Contents of This Book 34 1.1.3.1 Overall Organization of the Book 34 1.1.3.2 Contents of the Specific Parts 34 1.1.4 Approach and Style of This Book 38 1.1.4.1 The General Principle 38 1.1.4.2 On a Few Specific Choices 39 1.1.4.3 On the Presentation of Technical Details 40 1.1.4.4 Organizational Principles 40 1.1.4.5 A Call for Tolerance 41 1.1.4.6 Additional Comments Regarding Motivation 41 1.1.5 Standard Notations and Other Conventions 42 1.2 Computational Tasks and Models 43 1.2.1 Representation 44 1.2.2 Computational Tasks 44 1.2.2.1 Search Problems 45 1.2.2.2 Decision Problems 45 1.2.2.3 Promise Problems (an Advanced Comment) 46 1.2.3 Uniform Models (Algorithms) 46 1.2.3.1 Overview and General Principles 46 1.2.3.2 A Concrete Model: Turing Machines 48 1.2.3.3 Uncomputable Functions 52 1.2.3.4 Universal Algorithms 55 1.2.3.5 Time and Space Complexity 58 1.2.3.6 Oracle Machines 61 1.2.3.7 Restricted Models 62 1.2.4 Non-uniform Models (Circuits and Advice) 62 1.2.4.1 Boolean Circuits 63 1.2.4.2 Machines That Take Advice 66 1.2.4.3 Restricted Models 67 1.2.5 Complexity Classes 68 Chapter Notes 69 Chapter 2 P, NP, and NP-Completeness 70 2.1 The P Versus NP Question 72 2.1.1 The Search Version: Finding Versus Checking 73 2.1.1.1 The Class P as a Natural Class of Search Problems 74 2.1.1.2 The Class NP as Another Natural Class of Search Problems 75 2.1.1.3 The P Versus NP Question in Terms of Search Problems 75 2.1.2 The Decision Version: Proving Versus Verifying 76 2.1.2.1 The Class P as a Natural Class of Decision Problems 76 2.1.2.2 The Class NP and NP-proof Systems 77 2.1.2.3 The P Versus NP Question in Terms of Decision Problems 79 2.1.3 Equivalence of the Two Formulations 80 2.1.4 Two Technical Comments Regarding NP 81 2.1.5 The Traditional Definition of NP 81 2.1.6 In Support of P Different from NP 83 2.1.7 Philosophical Meditations 84 2.2 Polynomial-Time Reductions 84 2.2.1 The General Notion of a Reduction 85 2.2.1.1 The Actual Formulation 85 2.2.1.2 Special Cases 86 2.2.1.3 Terminology and a Brief Discussion 87 2.2.2 Reducing Optimization Problems to Search Problems 87 2.2.3 Self-Reducibility of Search Problems 89 2.2.3.1 Examples 90 2.2.3.2 Self-Reducibility of NP-Complete Problems 92 2.2.4 Digest and General Perspective 93 2.3 NP-Completeness 93 2.3.1 Definitions 94 2.3.2 The Existence of NP-Complete Problems 95 2.3.3 Some Natural NP-Complete Problems 97 2.3.3.1 Circuit and Formula Satisfiability: CSAT and SAT 98 2.3.3.2 Combinatorics and Graph Theory 103 2.3.4 NP Sets That Are Neither in P nor NP-Complete 107 2.3.5 Reflections on Complete Problems 111 2.4 Three Relatively Advanced Topics 113 2.4.1 Promise Problems 113 2.4.1.1 Definitions 114 2.4.1.2 Applications 116 2.4.1.3 The Standard Convention of Avoiding Promise Problems 117 2.4.2 Optimal Search Algorithms for NP 118 2.4.3 The Class coNP and Its Intersection with NP 120 Chapter Notes 123 Exercises 123 Chapter 3 Variations on P and NP 134 3.1 Non-uniform Polynomial Time (P/poly) 134 3.1.1 Boolean Circuits 135 3.1.2 Machines That Take Advice 137 3.2 The Polynomial-Time Hierarchy (PH) 139 3.2.1 Alternation of Quantifiers 140 3.2.2 Non-deterministic Oracle Machines 143 3.2.3 The P/poly Versus NP Question and PH 145 Chapter Notes 147 Exercises 147 Chapter 4 More Resources, More Power? 153 4.1 Non-uniform Complexity Hierarchies 154 4.2 Time Hierarchies and Gaps 155 4.2.1 Time Hierarchies 155 4.2.1.1 The Time Hierarchy Theorem 156 4.2.1.2 Impossibility of Speedup for Universal Computation 159 4.2.1.3 Hierarchy Theorem for Non-deterministic Time 160 4.2.2 Time Gaps and Speedup 162 4.3 Space Hierarchies and Gaps 165 Chapter Notes 165 Exercises 165 Chapter 5 Space Complexity 169 5.1 General Preliminaries and Issues 170 5.1.1 Important Conventions 170 5.1.2 On the Minimal Amount of Useful Computation Space 171 5.1.3 Time Versus Space 172 5.1.3.1 Two Composition Lemmas 172 5.1.3.2 An Obvious Bound 174 5.1.3.3 Subtleties Regarding Space-Bounded Reductions 175 5.1.3.4 Search Versus Decision 178 5.1.3.5 Complexity Hierarchies and Gaps 178 5.1.3.6 Simultaneous Time-Space Complexity 178 5.1.4 Circuit Evaluation 179 5.2 Logarithmic Space 179 5.2.1 The Class L 180 5.2.2 Log-Space Reductions 180 5.2.3 Log-Space Uniformity and Stronger Notions 181 5.2.4 Undirected Connectivity 181 5.2.4.1 The Basic Approach 183 5.2.4.2 The Actual Implementation 184 5.3 Non-deterministic Space Complexity 188 5.3.1 Two Models 188 5.3.2 NL and Directed Connectivity 190 5.3.2.1 Completeness and Beyond 190 5.3.2.2 Relating NSPACE to DSPACE 191 5.3.2.3 Complementation or NL = coNL 193 5.3.3 A Retrospective Discussion 197 5.4 PSPACE and Games 198 Chapter Notes 200 Exercises 201 Chapter 6 Randomness and Counting 210 6.1 Probabilistic Polynomial Time 211 6.1.1 Basic Modeling Issues 212 6.1.2 Two-Sided Error: The Complexity Class BPP 215 6.1.2.1 On the Power of Randomization 216 6.1.2.2. A Probabilistic Polynomial-Time Primality Test 218 6.1.3 One-Sided Error: The Complexity Classes RP and coRP 219 6.1.3.1 Testing Polynomial Identity 220 6.1.3.2 Relating BPP to RP 221 6.1.4 Zero-Sided Error: The Complexity Class ZPP 225 6.1.5 Randomized Log-Space 225 6.1.5.1 Definitional Issues 226 6.1.5.2 The Accidental Tourist Sees It All 227 6.2 Counting 228 6.2.1 Exact Counting 228 6.2.1.1 On the Power of #P 229 6.2.1.2 Completeness in #P 229 6.2.2 Approximate Counting 237 6.2.2.1 Relative Approximation for #Rdnf 238 6.2.2.2 Relative Approximation for #P 240 6.2.3 Searching for Unique Solutions 243 6.2.4 Uniform Generation of Solutions 246 6.2.4.1 Relation to Approximate Counting 247 6.2.4.2 A Direct Procedure for Uniform Generation 250 Chapter Notes 253 Exercises 255 Chapter 7 The Bright Side of Hardness 267 7.1 One-Way Functions 268 7.1.1 Generating Hard Instances and One-Way Functions 269 7.1.2 Amplification of Weak One-Way Functions 271 7.1.3 Hard-Core Predicates 276 7.1.4 Reflections on Hardness Amplification 281 7.2 Hard Problems in E 281 7.2.1 Amplification with Respect to Polynomial-Size Circuits 283 7.2.1.1 From Worst-Case Hardness to Mild Average-Case Hardness 284 7.2.1.2 Yao's XOR Lemma 286 7.2.1.3 List Decoding and Hardness Amplification 292 7.2.2 Amplification with Respect to Exponential-Size Circuits 296 7.2.2.1 Hard Regions 297 7.2.2.2 Hardness Amplification via Hard Regions 300 Chapter Notes 303 Exercises 303 Chapter 8 Pseudorandom Generators 310 Introduction 311 8.1 The General Paradigm 314 8.2 General-Purpose Pseudorandom Generators 316 8.2.1 The Basic Definition 317 8.2.2 The Archetypical Application 318 8.2.3 Computational Indistinguishability 321 8.2.3.1 The General Formulation 321 8.2.3.2 Relation to Statistical Closeness 322 8.2.3.3 Indistinguishability by Multiple Samples 322 8.2.4 Amplifying the Stretch Function 325 8.2.5 Constructions 327 8.2.5.1 A Simple Construction 327 8.2.5.2 An Alternative Presentation 328 8.2.5.3 A General Condition for the Existence of Pseudorandom Generators 329 8.2.6 Non-uniformly Strong Pseudorandom Generators 330 8.2.7 Stronger Notions and Conceptual Reflections 331 8.2.7.1 Stronger (Uniform-Complexity) Notions 332 8.2.7.2 Conceptual Reflections 332 8.3 Derandomization of Time-Complexity Classes 333 8.3.1 Defining Canonical Derandomizers 334 8.3.2 Constructing Canonical Derandomizers 336 8.3.2.1 The Construction and Its Consequences 336 8.3.2.2 Analyzing the Construction (i.e., Proof of Theorem 8.18) 338 8.3.3 Technical Variations and Conceptual Reflections 339 8.3.3.1 Construction 8.17 as a General Framework 340 8.3.3.2 Reflections Regarding Derandomization 341 8.4 Space-Bounded Distinguishers 341 8.4.1 Definitional Issues 342 8.4.2 Two Constructions 344 8.4.2.1 Sketches of the Proofs of Theorems 8.21 and 8.22 345 8.4.2.2 Derandomization of Space-Complexity Classes 349 8.5 Special-Purpose Generators 351 8.5.1 Pairwise Independence Generators 352 8.5.1.1 Constructions 352 8.5.1.2 Applications (a Brief Review) 354 8.5.2 Small-Bias Generators 355 8.5.2.1 Constructions 356 8.5.2.2 Applications (a Brief Review) 357 8.5.2.3 Generalization 358 8.5.3 Random Walks on Expanders 358 Chapter Notes 361 Exercises 363 Chapter 9 Probabilistic Proof Systems 375 Introduction and Preliminaries 376 9.1 Interactive Proof Systems 378 9.1.1 Motivation and Perspective 378 9.1.1.1 A Static Object Versus an Interactive Process 378 9.1.1.2 Prover and Verifier 379 9.1.1.3 Completeness and Soundness 380 9.1.2 Definition 380 9.1.3 The Power of Interactive Proofs 383 9.1.3.1 A Simple Example 383 9.1.3.2 The Full Power of Interactive Proofs 384 9.1.3.3 Sketch of the Proof of Theorem 9.4 385 9.1.4 Variants and Finer Structure: An Overview 389 9.1.4.1 Arthur-Merlin Games (Public-Coin Proof Systems) 390 9.1.4.2 Interactive Proof Systems with Two-Sided Error 390 9.1.4.3 A Hierarchy of Interactive Proof Systems 390 9.1.4.4 Something Completely Different 392 9.1.5 On Computationally Bounded Provers: An Overview 392 9.1.5.1 How Powerful Should the Prover Be? 392 9.1.5.2 Computational Soundness 393 9.2 Zero-Knowledge Proof Systems 394 9.2.1 Definitional Issues 395 9.2.1.1 A Wider Perspective: The Simulation Paradigm 395 9.2.1.2 The Basic Definitions 396 9.2.2 The Power of Zero-Knowledge 398 9.2.2.1 A Simple Example 398 9.2.2.2 The Full Power of Zero-Knowledge Proofs 400 9.2.3 Proofs of Knowledge -- A Parenthetical Subsection*-0pt 404 9.2.3.1 Abstract Reflections 404 9.2.3.2 A Concrete Treatment 404 9.3 Probabilistically Checkable Proof Systems 406 9.3.1 Definition 407 9.3.2 The Power of Probabilistically Checkable Proofs 409 9.3.2.1 Proving That NPPCP(poly,O(1)) 410 9.3.2.2 Overview of the First Proof of the PCP Theorem 414 9.3.2.3 Overview of the Second Proof of the PCP Theorem 420 9.3.3 PCP and Approximation 424 9.3.4 More on PCP Itself: An Overview 427 9.3.4.1 More on the PCP Characterization of NP 427 9.3.4.2 Stronger Forms of PCP-Systems for NP 428 9.3.4.3 PCP with Super-logarithmic Randomness 430 Chapter Notes 430 Exercises 432 Chapter 10 Relaxing the Requirements 442 10.1 Approximation 443 10.1.1 Search or Optimization 444 10.1.1.1 A Few Positive Examples 445 10.1.1.2 A Few Negative Examples 446 10.1.2 Decision or Property Testing 449 10.1.2.1 Definitional Issues 450 10.1.2.2 Two Models for Testing Graph Properties 451 10.1.2.3 Beyond Graph Properties 454 10.2 Average-Case Complexity 454 10.2.1 The Basic Theory 456 10.2.1.1 Definitional Issues 456 10.2.1.2 Complete Problems 461 10.2.1.3 Probabilistic Versions 468 10.2.2 Ramifications 468 10.2.2.1 Search Versus Decision 469 10.2.2.2 Simple Versus Samplable Distributions 471 Chapter Notes 477 10.2.2.3 Approximation 478 Exercises 479 Epilogue 487 Appendix A Glossary of Complexity Classes 489 A.1 Preliminaries 489 A.2 Algorithm-Based Classes 490 A.2.1 Time Complexity Classes 490 A.2.1.1 Classes Closely Related to Polynomial Time 490 A.2.1.2 Other Time Complexity Classes 492 A.2.2 Space Complexity Classes 493 A.3 Circuit-Based Classes 493 Appendix B On the Quest for Lower Bounds 495 B.1 Preliminaries 495 B.2 Boolean Circuit Complexity 497 B.2.1 Basic Results and Questions 498 B.2.2 Monotone Circuits 499 B.2.3 Bounded-Depth Circuits 499 B.2.4 Formula Size 500 B.3 Arithmetic Circuits 501 B.3.1 Univariate Polynomials 502 B.3.2 Multivariate Polynomials 502 B.4 Proof Complexity 504 B.4.1 Logical Proof Systems 506 B.4.2 Algebraic Proof Systems 506 B.4.3 Geometric Proof Systems 507 Appendix C On the Foundations of Modern Cryptography 508 C.1 Introduction and Preliminaries 508 C.1.1 The Underlying Principles 509 C.1.1.1 Coping with Adversaries 509 C.1.1.2 The Use of Computational Assumptions 510 C.1.2 The Computational Model 511 C.1.2.1 Efficient Computations and Infeasible ones 511 C.1.2.2 Randomized (or Probabilistic) Computations 511 C.1.3 Organization and Beyond 512 C.2 Computational Difficulty 513 C.2.1 One-Way Functions 513 C.2.2 Hard-Core Predicates 515 C.3 Pseudorandomness 516 C.3.1 Computational Indistinguishability 516 C.3.2 Pseudorandom Generators 517 C.3.3 Pseudorandom Functions 518 C.4 Zero-Knowledge 520 C.4.1 The Simulation Paradigm 520 C.4.2 The Actual Definition 520 C.4.3 A General Result and a Generic Application 521 C.4.3.1 Commitment Schemes 522 C.4.3.2 A Generic Application 522 C.4.4 Definitional Variations and Related Notions 523 C.4.4.1 Definitional Variations 523 C.4.4.2 Related Notions: POK, NIZK, and WI 525 C.5 Encryption Schemes 526 C.5.1 Definitions 528 C.5.2 Constructions 530 C.5.3 Beyond Eavesdropping Security 531 C.6 Signatures and Message Authentication 533 C.6.1 Definitions 534 C.6.2 Constructions 535 C.7 General Cryptographic Protocols 537 C.7.1 The Definitional Approach and Some Models 538 C.7.1.1 Some Parameters Used in Defining Security Models 538 C.7.1.2 Example: Multi-party Protocols with Honest Majority 540 C.7.1.3 Another Example: Two-Party Protocols Allowing Abort 541 C.7.2 Some Known Results 543 C.7.3 Construction Paradigms and Two Simple Protocols 543 C.7.3.1 Passively Secure Computation with Shares 544 C.7.3.2 From passively Secure Protocols to Actively Secure Ones 546 C.7.4 Concluding Remarks 548 Appendix D Probabilistic Preliminaries and Advanced Topics in Randomization 549 D.1 Probabilistic Preliminaries 549 D.1.1 Notational Conventions 549 D.1.2 Three Inequalities 550 D.1.2.1 Markov's Inequality 551 D.1.2.2 Chebyshev's Inequality 551 D.1.2.3 Chernoff Bound 552 D.1.2.4 Pairwise Independent Versus Totally Independent Sampling 553 D.2 Hashing 554 D.2.1 Definitions 554 D.2.2 Constructions 555 D.2.3 The Leftover Hash Lemma 555 D.3 Sampling 559 D.3.1 Formal Setting 559 D.3.2 Known Results 560 D.3.3 Hitters 561 D.4 Randomness Extractors 562 D.4.1 Definitions and Various Perspectives 563 D.4.1.1 The Main Definition 563 D.4.1.2 Extractors as Averaging Samplers 564 D.4.1.3 Extractors as Randomness-Efficient Error Reductions 565 D.4.1.4 Other Perspectives 566 D.4.2 Constructions 567 D.4.2.1 Some Known Results 567 D.4.2.2 The Pseudorandomness Connection 568 D.4.2.3 Recommended Reading 570 Appendix E Explicit Constructions 571 E.1 Error-Correcting Codes 572 E.1.1 Basic Notions 572 E.1.2 A Few Popular Codes 573 E.1.2.1 A Mildly Explicit Version of Proposition E.1 574 E.1.2.2 The Hadamard Code 575 E.1.2.3 The Reed--Solomon Code 575 E.1.2.4 The Reed--Muller Code 575 E.1.2.5 Binary Codes of Constant Relative Distance and Constant Rate 576 E.1.3 Two Additional Computational Problems 577 E.1.4 A List-Decoding Bound 579 E.2 Expander Graphs 580 E.2.1 Definitions and Properties 581 E.2.1.1 Two Mathematical Definitions 581 E.2.1.2 Two Levels of Explicitness 582 E.2.1.3 Two Properties 583 E.2.2 Constructions 587 E.2.2.1 The Margulis-Gabber-Galil Expander 587 E.2.2.2 The Iterated Zig-Zag Construction 588 Appendix F Some Omitted Proofs 592 F.1. Proving That PH Reduces to #P 592 F.2. Proving That IP( f ) ⊆ AM(O( f )) ⊆ AM( f ) 598 F.2.1 Emulating General Interactive Proofs by AM-Games 598 F.2.1.1 Overview 598 F.2.1.2 Random Selection 600 F.2.1.3 The Iterated Partition Protocol 601 F.2.2 Linear Speedup for AM 604 F.2.2.1 The Basic Switch (from MA to AM) 605 F.2.2.2 The Augmented Switch (from [MAMA]j to [AMA]jA) 607 Appendix G Some Computational Problems 609 G.1 Graphs 609 G.2 Boolean Formulae 611 G.3 Finite Fields, Polynomials, and Vector Spaces 612 G.4 The Determinant and the Permanent 613 G.5 Primes and Composite Numbers 613 Bibliography 615 Index 627

This book offers a comprehensive perspective to modern topics in complexity theory, which is a central field of the theoretical foundations of computer science. It addresses the looming question of what can be achieved within a limited amount of time with or without other limited natural computational resources. Can be used as an introduction for advanced undergraduate and graduate students as either a textbook or for self-study, or to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems.