Complexity Theory: A Modern Approach

Sanjeev Arora and Boaz Barak

Princeton University

This is a draft of a textbook on computational complexity theory. It is intended as a text for an advanced undergraduate course or introductory graduate course, or as a reference for researchers and students in computer science and allied fields such as mathematics and physics. We plan to keep this rough draft on the web, even after the book is published, as a resource for teachers and students from developing countries.

Update: We have pushed back the publication date, and now plan to submit the book by May 2007, the expected publication date is January 2008.

We would be grateful for comments, especially of the following kind:

  • Places in the book that are difficult for non-specialists, e.g., due to inadequate explanations or use of jargon.
  • Incorrect proofs or calculations.
  • Topics you normally teach but are missing (please check the table of contents for topics we still plan to add).
  • Places where, in your experience, students get confused and need additional explanations or a worked-out exercise.
  • Missing or incorrect references. (We are working on the references and historical notes, but would like to know about any inaccuracies, for which we apologize in advance.)

We are grateful for the comments we already received, which we are still working on implementing. Please send any additional comments to

May the force of P and NP be with you


WEB DRAFT

(All the files below are in acrobat PDF format.)

Get the whole draft - 4.1MB pdf (click here for the previous (Nov 06) version)

Part I: Basic Complexity Classes

  1. The computational model - and why it doesn't matter. Definition of Turing machine, efficient universal TM, the class P.
  2. NP and NP completeness. NP, Cook-Levin Theorem, NP-completeness, search vs. decision.
  3. Diagonalization Time, Non-deterministic time, and space hierarchy theorems, Ladner's theorem, oracle machines and proof that relativized methods can't resolve P vs. NP.
  4. Space Complexity PSPACE, L, NL. TQBF is PSPACE complete, Savitch's Theorem, Path is NL-complete, NL=coNL.
  5. The polynomial hierarchy and alternations. Definitions of PH via alternating quantifiers and alternating machines, conjecture it doesn't collapse, time-space tradeoffs for SAT.
  6. Circuits. Boolean circuits and the class Ppoly. Definition using advice. Karp-Lipton theorem. Non-uniform hierarchy theorem. circuit-satisfiability and alternative proof for Cook-Levin theorem.
  7. Randomized Computation BPP, RP, coRP, ZPP. Examples of probabilistic algorithms. Error reduction via repetition. BPP in P/poly and PH. Randomized reductions, randomized logspace algorithms. Second eigenvalue and analysis of random walks.
  8. Interactive Proofs IP, AM. Graph non-isormorphism in AM. IP=PSPACE.
  9. Complexity of Counting #P. #P-completeness and Valiant's theorem. Toda's theorem.
  10. Cryptography One-way functions, pseudorandom generators: prediction vs. distinguishing. Goldreich-Levin theorem. Zero knowledge and ZK proof for graph isomorphism. Overview of advanced topics in cryptography.

Part II: Lower bounds for concrete computational models

  1. Decision Trees certificate complexity, randomized complexity, sorting lowerbounds
  2. Communication Complexity Lowerbound methods (fooling set, rank, tiling, discrepancy), multiparty communication complexity
  3. Circuit lowerbounds. Hastad switching lemma, lowerbounds for monotone circuits, frontier of circuit lowerbounds, approaches using communication complexity.
  4. Algebraic complexity Algebraic trees and circuits, Blum-Shub-Smale model.

Part III: Advanced Topics

  1. Average Case Complexity: Levin's Theory DistNP and its complete problems.
  2. Derandomization, Expanders and Extractors Pseudorandom generators from average-case hardness - the NW generators. Extractors from hash functions. Zig-zag construction of expanders, reingold's deterministic logspace algorithm for undirected connectivity. Trevisan's extractor from NW.
  3. Hardness amplification and error correcting codes Worst-case to average case reduction. Error correcting codes. Pseudoarndom generators from worst-case assumptions. List decoding and its use for hardness amplification.
  4. PCP and hardness of approximation. NP in PCP(poly,1). The PCP theorem (Dinur's proof). Independent set is hard to approximate within a polynomial factor.
  5. More PCP Theorems and the Fourier Transform Technique Fourier transforms over GF(2)^n. Analysis of linearity testing. Hastad's 3-query PCP, 3SAT is hard to 7/8+epsilon approximate. Learning fourier coefficients (Goldreich-Levin / Kushilevits-Mansour)
  6. Quantum Computation Quantum computation and the class QBP. Shor's factoring algorithm.
  7. Logic in complexity theory Proof complexity.
  8. Why are circuit lower bounds so difficult? Natural proofs.