## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## Book Description

This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. More than 300 exercises are included with a selected hint set. The book starts with a broad introduction to the field and progresses to advanced results. Contents include: definition of Turing machines and basic time and space complexity classes, probabilistic algorithms, interactive proofs, cryptography, quantum computation, lower bounds for concrete computational models (decision trees, communication complexity, constant depth, algebraic and monotone circuits, proof complexity), average-case complexity and hardness amplification, derandomization and pseudorandom constructions, and the PCP theorem.

## Table of Contents

1. Cover
2. Half-title
3. Title
4. Copyright
5. Dedication
6. Contents
7. About this book
8. Acknowledgments
9. Introduction
10. Chapter 0 Notational conventions
1. Standard notation
2. Strings
3. Additional notation
4. 0.1 Representing Objects as Strings
5. 0.2 Decision Problems/Languages
6. 0.3 Big-Oh Notation
7. Exercises
11. Part ONE Basic Complexity Classes
1. CHAPTER 1 The computational model—and why it doesn't matter
1. 1.1 Modeling Computation: What You Really Need to Know
2. 1.2 The Turing Machine
3. 1.3 Efficiency and Running Time
4. 1.4 Machines as Strings and the Universal Turing Machine
1. 1.4.1 The universal Turing machine
5. 1.5 Uncomputability: An Introduction
6. 1.6 The Class P
7. 1.7 Proof of Theorem 1.9: Universal Simulation in O(TlogT)-time
8. Chapter Notes and History
9. Exercises
2. CHAPTER 2 NP and NP completeness
1. 2.1 The Class NP
2. 2.2 Reducibility and NP-Completeness
3. 2.3 The Cook-Levin Theorem: Computation is Local
4. 2.4 The Web of Reductions
5. 2.5 Decision Versus Search
6. 2.6 CONP, EXP, and NEXP
7. 2.7 More thoughts about P, NP, and all that
8. Chapter Notes and History
9. Exercises
3. CHAPTER 3 Diagonalization
1. Machines as strings and the universal TM
2. 3.1 Time Hierarchy Theorem
3. 3.2 Nondeterministic Time Hierarchy Theorem
4. 3.3 Ladner's Theorem: Existence of NP-intermediate problems
5. 3.4 Oracle Machines and the Limits of Diagonalization
6. Chapter Notes and History
7. Exercises
4. CHAPTER 4 Space complexity
1. 4.1 Definition of Space-Bounded Computation
2. 4.2 PSPACE Completeness
3. 4.3 NL Completeness
4. Chapter Notes and History
5. Exercises
5. CHAPTER 5 The polynomial hierarchy and alternations
1. 5.1 The Class…
2. 5.2 The Polynomial Hierarchy
3. 5.3 Alternating Turing Machines
4. 5.4 Time versus alternations: time-space tradeoffs for sat
5. 5.5 Defining the Hierarchy via Oracle Machines
6. Chapter Notes and History
7. Exercises
6. CHAPTER 6 Boolean circuits
1. 6.1 Boolean Circuits and P/poly
2. 6.2 Uniformly Generated Circuits
3. 6.3 Turing Machines that Take Advice
4. 6.4 P/poly and NP
5. 6.5 Circuit Lower Bounds
6. 6.6 Nonuniform Hierarchy Theorem
7. 6.7 Finer Gradations Among Circuit Classes
8. 6.8 Circuits of Exponential Size
9. Chapter Notes and History
10. Exercises
7. CHAPTER 7 Randomized computation
1. 7.1 Probabilistic Turing Machines
2. 7.2 Some Examples of PTMs
3. 7.3 One-Sidedand "Zero-Sided'' Error: RP, coRP, ZPP
4. 7.4 The Robustness of Our Definitions
5. 7.5 Relationship between BPP and other classes
1. 7.5.1 BPPP…/poly
2. 7.5.2 BPP is in PH
3. 7.5.3 Hierarchy theorems and complete problems?
6. 7.6 Randomized Reductions
7. 7.7 Randomized Space-Bounded Computation
8. Chapter Notes and History
9. Exercises
8. CHAPTER 8 Interactive proofs
1. 8.1 Interactive Proofs: Some Variations
2. 8.2 Publiccoins and AM
1. 8.2.1 Simulating private coins
2. 8.2.2 Set lower bound protocol
3. 8.2.3 Sketch of proof of Theorem 8.12
4. 8.2.4 Can GI be NP-complete?
3. 8.3 IP = PSPACE
1. 8.3.1 Arithmetization
2. 8.3.2 Interactive protocol for #SATD
3. 8.3.3 Protocol for TQBF: proof of Theorem 8.19
4. 8.4 The Power of the Prover
5. 8.5 Multiprover Interactive Proofs (mip)
6. 8.6 Program Checking
7. 8.7 Interactive Proof for the Permanent
8. Chapter Notes and History
9. Exercises
9. CHAPTER 9 Cryptography
1. 9.1 Perfect Secrecy and its Limitations
2. 9.2 Computational Security, One-Way Functions, and Pseudorandom Generators
3. 9.3 Pseudorandom Generators from One-Way Permutations
1. 9.3.1 Unpredictability implies pseudorandomness
2. 9.3.2 Proof of Lemma 9.10: The Goldreich-Levin Theorem
4. 9.4 Zero Knowledge
5. 9.5 Some Applications
6. Chapter Notes and History
7. Exercises
10. CHAPTER 10 Quantum computation
1. 10.1 Quantum Weirdness: The Two-Slit Experiment
2. 10.2 Quantum Superposition and Qubits
1. 10.2.1 EPR paradox
3. 10.3 Definition of Quantum Computation and BQP
4. 10.4 Grover's Search Algorithm
5. 10.5 Simon's Algorithm
6. 10.6 Shor's Algorithm: Integer Factorization Using Quantum Computers
1. Shor’s ideas in nutshell
2. 10.6.1 The Fourier transform over ZM
3. 10.6.2 Quantum fourier transform over ZM
4. 10.6.3 Shor's order-finding algorithm
5. 10.6.4 Reducing factoring to order finding
6. 10.6.5 Rational approximation of real numbers
7. 10.7 BQP and Classical Complexity Classes
8. Chapter Notes and History
9. Exercises
11. CHAPTER 11 PCP theorem and hardness of approximation: An introduction
1. 11.1 Motivation: approximate solutions to NP-hard optimization problems
2. 11.2 Two views of the PCP Theorem
3. 11.3 Equivalence of the Two Views
4. 11.4 Hardness of Approximation for Vertex Cover and Independent Set
5. 11.5 NP .o PCP(poly(n), 1): PCP FROM THE WALSH-HADAMARD CODE
1. 11.5.1 Tool: Linearity testing and the Walsh-Hadamard code
2. 11.5.2 Proof of Theorem 11.19
6. Chapter Notes and History
7. Exercises
12. Part TWO Lower bounds for Concrete computational models
1. CHAPTER 12 Decision trees
1. 12.1 Decision Trees and Decision Tree Complexity
2. 12.2 Certificate Complexity
3. 12.3 Randomized Decision Trees
4. 12.4 Some Techniques for Proving Decision Tree Lower Bounds
5. Chapter Notes and History
6. Exercises
2. CHAPTER 13 Communication complexity
1. 13.1 Definition of Two-Party Communication Complexity
2. 13.2 Lower Bound Methods
3. 13.3 Multiparty Communication Complexity
4. 13.4 Overview of Other Communication Models
5. Chapter Notes and History
6. Exercises
3. CHAPTER 14 Circuit lower bounds Complexity theory’s Waterloo
1. 14.1 AC0 AND HÅSTAD’S SWITCHING LEMMA
1. 14.1.1 Håstad’s Switching Lemma
2. 14.1.2 Proof of the Switching Lemma (Lemma 14.2)
2. 14.2 Circuits With "Counters": ACC
3. 14.3 Lower Bounds for Monotone Circuits
1. 14.3.1 Proving Theorem 14.7
4. 14.4 Circuit Complexity: The Frontier
5. 14.5 Approaches Using Communication Complexity
6. Chapter Notes and History
7. Exercises
4. CHAPTER 15 Proof complexity
1. 15.1 Some Examples
2. 15.2 Propositional Calculus and Resolution
3. 15.3 Other Proof Systems: A Tour D'Horizon
4. 15.4 Metamathematical Musings
5. Chapter Notes and History
6. Exercises
5. CHAPTER 16 Algebraic computation models
1. 16.1 Algebraic Straight-Line Programs and Algebraic Circuits
2. 16.2 Algebraic Computation Trees
3. 16.3 The Blum-Shub-Smale Model
4. Chapter Notes and History
5. Exercises
13. Part THREE Advanced Topics
1. CHAPTER 17 Complexity of counting
1. 17.1 Examples of Counting Problems
2. 17.2 The Class #P
3. 17.3 #P Completeness
1. 17.3.1 Permanent and Valiant's Theorem
2. 17.3.2 Approximate solutions to #P problems
4. 17.4 TODA.fS THEOREM: PH .o P#SAT
5. 17.5 Open Problems
6. Chapter Notes and History
7. Exercises
2. CHAPTER 18 Average case complexity: Levin's theory
1. 18.1 Distributional Problems and distP
2. 18.2 Formalization of "Real-Life Distributions"
3. 18.3 distNP and its complete problems
4. 18.4 Philosophical and Practical Implications
5. Chapter Notes and History
6. Exercises
3. CHAPTER 19 Hardness amplification and error-correcting codes
1. 19.1 Mild to Strong Hardness: Yao's XOR Lemma
2. 19.2 Tool: Error-Correcting Codes
3. 19.3 Efficient Decoding
4. 19.4 Local Decoding and Hardness Amplification
5. 19.5 List Decoding
6. 19.6 Local List Decoding: Getting to BPP =P
4. CHAPTER 20 Derandomization
1. 20.1 Pseudorandom Generators and Derandomization
2. 20.2 Proof of Theorem 20.6: Nisan-Wigderson Construction
1. 20.2.1 Two toy examples
2. 20.2.2 The NW construction
3. 20.3 Derandomization Under Uniform Assumptions
4. 20.4 Derandomization Requires Circuit Lower Bounds
5. Chapter Notes and History
6. Exercises
5. CHAPTER 21 Pseudorandom constructions: Expanders and extractors
1. 21.1 Random Walks and Eigenvalues
1. 21.1.1 Distributions as vectors and the parameter (G)
2. 21.1.2 Analysis of the randomized algorithm for undirected connectivity
2. 21.2 Expander Graphs
3. 21.3 Explicit Construction of Expander Graphs
4. 21.4 Deterministic Logspace Algorithm for Undirected Connectivity
5. 21.5 Weak Random Sources and Extractors
6. 21.6 Pseudorandom Generators for Space-Bounded Computation
7. Chapter Notes and History
8. Exercises
6. CHAPTER 22 Proofs of PCP theorems and the Fourier transform technique
1. 22.1 Constraint Satisfaction Problems with Nonbinary Alphabet
2. 22.2 Proof of the PCP Theorem
1. 22.2.1 Proof outline for the PCP Theorem
2. 22.2.2 Dinur's gap amplification: Proof of Lemma 22.5
3. 22.2.3 Expanders, walks, and hardness of approximating INDSET
4. 22.2.4 Dinur's gap amplification
5. 22.2.5 Alphabet reduction: Proof of Lemma 22.6
3. 22.3 Hardness of 2CSPW: Trade off between gap and alphabet size
4. 22.4 HÅSTAD’S 3-BIT PCP THEOREMAND HARDNESS OF MAX-3SAT
5. 22.5 Tool: The Fourier Transform Technique
6. 22.6 Coordinate Functions, Long Code, and its Testing
7. 22.7 Proof of Theorem 22.16
8. 22.8 Hardness of Approximating SET-COVER
9. 22.9 Other PCP Theorems: A Survey
10. 22.A Transforming qCSP instancesinto ``nice''instances
11. Chapter Notes and History
12. Exercises
7. 23 Why are circuit lower bounds so difficult?
1. 23.1 Definition of Natural Proofs
2. 23.2 What's So Natural About Natural Proofs?
3. 23.3 Proof of Theorem 23.1
4. 23.4 An "Unnatural" Lower Bound
5. 23.5 APhilosophical View
6. Chapter Notes and History
7. Exercises
14. APPENDIX Mathematical background
1. A.1 Sets, Functions, Pairs, Strings, Graphs, Logic
2. A.2 Probability Theory
1. Inclusion exclusion principle
2. A.2.1 Random variables and expectations
3. A.2.2 The averaging argument
4. A.2.3 Conditional probability and independence
5. A.2.4 Deviation upper bounds
6. A.2.5 Some other inequalities
7. A.2.6 Statistical distance
3. A.3 Number Theory and Groups
4. A.4 Finite Fields
5. A.5 Basic Facts from Linear Algebra
6. A.6 Polynomials
15. Hints for selected exercises
16. Main theorems and definitions
17. Bibliography
18. Index
19. Complexity class index