| |
| |
| List of Figures | |
| |
| |
| Preface | |
| |
| |
| Organization and Chapter Summaries | |
| |
| |
| Acknowledgments | |
| |
| |
| |
| Introduction and Preliminaries | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| A Brief Overview of Complexity Theory | |
| |
| |
| |
| Characteristics of Complexity Theory | |
| |
| |
| |
| Contents of This Book | |
| |
| |
| |
| Approach and Style of This Book | |
| |
| |
| |
| Standard Notations and Other Conventions | |
| |
| |
| |
| Computational Tasks and Models | |
| |
| |
| |
| Representation | |
| |
| |
| |
| Computational Tasks | |
| |
| |
| |
| Uniform Models (Algorithms) | |
| |
| |
| |
| Non-uniform Models (Circuits and Advice) | |
| |
| |
| |
| Complexity Classes | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| P, NP, and NP-Completeness | |
| |
| |
| |
| The P Versus NP Question | |
| |
| |
| |
| The Search Version: Finding Versus Checking | |
| |
| |
| |
| The Decision Version: Proving Versus Verifying | |
| |
| |
| |
| Equivalence of the Two Formulations | |
| |
| |
| |
| Two Technical Comments Regarding NP | |
| |
| |
| |
| The Traditional Definition of NP | |
| |
| |
| |
| In Support of P Different from NP | |
| |
| |
| |
| Philosophical Meditations | |
| |
| |
| |
| Polynomial-Time Reductions | |
| |
| |
| |
| The General Notion of a Reduction | |
| |
| |
| |
| Reducing Optimization Problems to Search Problems | |
| |
| |
| |
| Self-Reducibility of Search Problems | |
| |
| |
| |
| Digest and General Perspective | |
| |
| |
| |
| NP-Completeness | |
| |
| |
| |
| Definitions | |
| |
| |
| |
| The Existence of NP-Complete Problems | |
| |
| |
| |
| Some Natural NP-Complete Problems | |
| |
| |
| |
| NP Sets That Are Neither in P nor NP-Complete | |
| |
| |
| |
| Reflections on Complete Problems | |
| |
| |
| |
| Three Relatively Advanced Topics | |
| |
| |
| |
| Promise Problems | |
| |
| |
| |
| Optimal Search Algorithms for NP | |
| |
| |
| |
| The Class coNP and Its Intersection with NP | |
| |
| |
| Chapter Notes | |
| |
| |
| Exercises | |
| |
| |
| |
| Variations on P and NP | |
| |
| |
| |
| Non-uniform Polynomial Time (P/poly) | |
| |
| |
| |
| Boolean Circuits | |
| |
| |
| |
| Machines That Take Advice | |
| |
| |
| |
| The Polynomial-Time Hierarchy (PH) | |
| |
| |
| |
| Alternation of Quantifiers | |
| |
| |
| |
| Non-deterministic Oracle Machines | |
| |
| |
| |
| The P/poly Versus NP Question and PH | |
| |
| |
| Chapter Notes | |
| |
| |
| Exercises | |
| |
| |
| |
| More Resources, More Power? | |
| |
| |
| |
| Non-uniform Complexity Hierarchies | |
| |
| |
| |
| Time Hierarchies and Gaps | |
| |
| |
| |
| Time Hierarchies | |
| |
| |
| |
| Time Gaps and Speedup | |
| |
| |
| |
| Space Hierarchies and Gaps | |
| |
| |
| Chapter Notes | |
| |
| |
| Exercises | |
| |
| |
| |
| Space Complexity | |
| |
| |
| |
| General Preliminaries and Issues | |
| |
| |
| |
| Important Conventions | |
| |
| |
| |
| On the Minimal Amount of Useful Computation Space | |
| |
| |
| |
| Time Versus Space | |
| |
| |
| |
| Circuit Evaluation | |
| |
| |
| |
| Logarithmic Space | |
| |
| |
| |
| The Class L | |
| |
| |
| |
| Log-Space Reductions | |
| |
| |
| |
| Log-Space Uniformity and Stronger Notions | |
| |
| |
| |
| Undirected Connectivity | |
| |
| |
| |
| Non-deterministic Space Complexity | |
| |
| |
| |
| Two Models | |
| |
| |
| |
| NL and Directed Connectivity | |
| |
| |
| |
| A Retrospective Discussion | |
| |
| |
| |
| PSPACE and Games | |
| |
| |
| Chapter Notes | |
| |
| |
| Exercises | |
| |
| |
| |
| Randomness and Counting | |
| |
| |
| |
| Probabilistic Polynomial Time | |
| |
| |
| |
| Basic Modeling Issues | |
| |
| |
| |
| Two-Sided Error: The Complexity Class BPP | |
| |
| |
| |
| One-Sided Error: The Complexity Classes RP and coRP | |
| |
| |
| |
| Zero-Sided Error: The Complexity Class ZPP | |
| |
| |
| |
| Randomized Log-Space | |
| |
| |
| |
| Counting | |
| |
| |
| |
| Exact Counting | |
| |
| |
| |
| Approximate Counting | |
| |
| |
| |
| Searching for Unique Solutions | |
| |
| |
| |
| Uniform Generation of Solutions | |
| |
| |
| Chapter Notes | |
| |
| |
| Exercises | |
| |
| |
| |
| The Bright Side of Hardness | |
| |
| |
| |
| One-Way Functions | |
| |
| |
| |
| Generating Hard Instances and One-Way Functions | |
| |
| |
| |
| Amplification of Weak One-Way Functions | |
| |
| |
| |
| Hard-Core Preicates | |
| |
| |
| |
| Reflections on Hardness Amplification | |
| |
| |
| |
| Hard Problems in E | |
| |
| |
| |
| Amplification with Respect to Polynomial-Size Circuits | |
| |
| |
| |
| Amplification with Respect to Exponential-Size Circuits | |
| |
| |
| Chapter Notes | |
| |
| |
| Exercises | |
| |
| |
| |
| Pseudorandom Generators | |
| |
| |
| Introduction | |
| |
| |
| |
| The General Paradigm | |
| |
| |
| |
| General-Purpose Pseudorandom Generators | |
| |
| |
| |
| The Basic Definition | |
| |
| |
| |
| The Archetypical Application | |
| |
| |
| |
| Computational Indistinguishability | |
| |
| |
| |
| Amplifying the Stretch Function | |
| |
| |
| |
| Constructions | |
| |
| |
| |
| Non-uniformly Strong Pseudorandom Generators | |
| |
| |
| |
| Stronger Notions and Conceptual Reflections | |
| |
| |
| |
| Derandomization of Time-Complexity Classes | |
| |
| |
| |
| Defining Canonical Derandomizers | |
| |
| |
| |
| Constructing Canonical Derandomizers | |
| |
| |
| |
| Technical Variations and Conceptual Reflections | |
| |
| |
| |
| Space-Bounded Distinguishers | |
| |
| |
| |
| Definitional Issues | |
| |
| |
| |
| Two Constructions | |
| |
| |
| |
| Special-Purpose Generators | |
| |
| |
| |
| Pairwise Independence Generators | |
| |
| |
| |
| Small-Bias Generators | |
| |
| |
| |
| Random Walks on Expanders | |
| |
| |
| Chapter Notes | |
| |
| |
| Exercises | |
| |
| |
| |
| Probabilistic Proof Systems | |
| |
| |
| Introduction and Preliminaries | |
| |
| |
| |
| Interactive Proof Systems | |
| |
| |
| |
| Motivation and Perspective | |
| |
| |
| |
| Definition | |
| |
| |
| |
| The Power of Interactive Proofs | |
| |
| |
| |
| Variants and Finer Structure: An Overview | |
| |
| |
| |
| On Computationally Bounded Provers: An Overview | |
| |
| |
| |
| Zero-Knowledge Proof Systems | |
| |
| |
| |
| Definitional Issues | |
| |
| |
| |
| The Power of Zero-Knowledge | |
| |
| |
| |
| Proofs of Knowledge - A Parenthetical Subsection | |
| |
| |
| |
| Probabilistically Checkable Proof Systems | |
| |
| |
| |
| Definition | |
| |
| |
| |
| The Power of Probabilistically Checkable Proofs | |
| |
| |
| |
| PCP and Approximation | |
| |
| |
| |
| More on PCP Itself: An Overview | |
| |
| |
| Chapter Notes | |
| |
| |
| Exercises | |
| |
| |
| |
| Relaxing the Requirements | |
| |
| |
| |
| Approximation | |
| |
| |
| |
| Search or Optimization | |
| |
| |
| |
| Decision or Property Testing | |
| |
| |
| |
| Average-Case Complexity | |
| |
| |
| |
| The Basic Theory | |
| |
| |
| |
| Ramifications | |
| |
| |
| Chapter Notes | |
| |
| |
| Exercises | |
| |
| |
| Epilogue | |
| |
| |
| |
| Glossary of Complexity Classes | |
| |
| |
| |
| Preliminaries | |
| |
| |
| |
| Algorithm-Based Classes | |
| |
| |
| |
| Time Complexity Classes | |
| |
| |
| |
| Space Complexity Classes | |
| |
| |
| |
| Circuit-Based Classes | |
| |
| |
| |
| On the Quest for Lower Bounds | |
| |
| |
| |
| Preliminaries | |
| |
| |
| |
| Boolean Circuit Complexity | |
| |
| |
| |
| Basic Results and Questions | |
| |
| |
| |
| Monotone Circuits | |
| |
| |
| |
| Bounded-Depth Circuits | |
| |
| |
| |
| Formula Size | |
| |
| |
| |
| Arithmetic Circuits | |
| |
| |
| |
| Univariate Polynomials | |
| |
| |
| |
| Multivariate Polynomials | |
| |
| |
| |
| Proof Complexity | |
| |
| |
| |
| Logical Proof Systems | |
| |
| |
| |
| Algebraic Proof Systems | |
| |
| |
| |
| Geometric Proof Systems | |
| |
| |
| |
| On the Foundations of Modern Cryptography | |
| |
| |
| |
| Introduction and Preliminaries | |
| |
| |
| |
| The Underlying Principles | |
| |
| |
| |
| The Computational Model | |
| |
| |
| |
| Organization and Beyond | |
| |
| |
| |
| Computational Difficulty | |
| |
| |
| |
| One-Way Functions | |
| |
| |
| |
| Hard-Core Predicates | |
| |
| |
| |
| Pseudorandomness | |
| |
| |
| |
| Computational Indistinguishability | |
| |
| |
| |
| Pseudorandom Generators | |
| |
| |
| |
| Pseudorandom Functions | |
| |
| |
| |
| Zero-Knowledge | |
| |
| |
| |
| The Simulation Paradigm | |
| |
| |
| |
| The Actual Definition | |
| |
| |
| |
| A General Result and a Generic Application | |
| |
| |
| |
| Definitional Variations and Related Notions | |
| |
| |
| |
| Encryption Schemes | |
| |
| |
| |
| Definitions | |
| |
| |
| |
| Constructions | |
| |
| |
| |
| Beyond Eavesdropping Security | |
| |
| |
| |
| Signatures and Message Authentication | |
| |
| |
| |
| Definitions | |
| |
| |
| |
| Constructions | |
| |
| |
| |
| General Cryptographic Protocols | |
| |
| |
| |
| The Definitional Approach and Some Models | |
| |
| |
| |
| Some Known Results | |
| |
| |
| |
| Construction Paradigms and Two Simple Protocols | |
| |
| |
| |
| Concluding Remarks | |
| |
| |
| |
| Probabilistic Preliminaries and Advanced Topics in Randomization | |
| |
| |
| |
| Probabilistic Preliminaries | |
| |
| |
| |
| Notational Conventions | |
| |
| |
| |
| Three Inequalities | |
| |
| |
| |
| Hashing | |
| |
| |
| |
| Definitions | |
| |
| |
| |
| Constructions | |
| |
| |
| |
| The Leftover Hash Lemma | |
| |
| |
| |
| Sampling | |
| |
| |
| |
| Formal Setting | |
| |
| |
| |
| Known Results | |
| |
| |
| |
| Hitters | |
| |
| |
| |
| Randomnes Extractors | |
| |
| |
| |
| Definitions and Various Perspectives | |
| |
| |
| |
| Constructions | |
| |
| |
| |
| Explicit Constructions | |
| |
| |
| |
| Error-Correcting Codes | |
| |
| |
| |
| Basic Notions | |
| |
| |
| |
| A Few Popular Codes | |
| |
| |
| |
| Two Additional Computational Problems | |
| |
| |
| |
| A List-Decoding Bound | |
| |
| |
| |
| Expander Graphs | |
| |
| |
| |
| Definitions and Properties | |
| |
| |
| |
| Constructions | |
| |
| |
| |
| Some Omitted Proofs | |
| |
| |
| |
| Proving That PH Reduces to #P | |
| |
| |
| |
| Proving That IP(f) [characters not reproducible] AM(O(f)) [characters not reproducible] AM(f) | |
| |
| |
| |
| Emulating General Interactive Proofs by AM-Games | |
| |
| |
| |
| Linear Speedup for AM | |
| |
| |
| |
| Some Computational Problems | |
| |
| |
| |
| Graphs | |
| |
| |
| |
| Boolean Formulae | |
| |
| |
| |
| Finite Fields, Polynomials, and Vector Spaces | |
| |
| |
| |
| The Determinant and the Permanent | |
| |
| |
| |
| Primes and Composite Numbers | |
| |
| |
| Bibliography | |
| |
| |
| Index | |