Un livre en ligne sur la théorie de la complexité :

Complexity Theory: A Modern Approach / Sanjeev Arora and Boaz Barak ^[1]

avec un chapitre sur le calcul quantique.
Voici la table des matières :

Part I: Basic Complexity Classes

1. The computational model – and why it doesn’t matter. ^[2] Definition of Turing machine, efficient universal TM, the class P.
2. NP and NP completeness. ^[3] NP, Cook-Levin Theorem, NP-completeness, search vs. decision.
3. Space Complexity ^[4] PSPACE, L, NL. TQBF is PSPACE complete, Savitch’s Theorem, Path is NL-complete, NL=coNL.
4. Diagonalization ^[5] Time, Non-deterministic time, and space hierarchy theorems, Ladner’s theorem, oracle machines and proof that relativized methods can’t resolve P vs. NP.
5. The polynomial hierarchy and alternations. ^[6] Definitions of PH via alternating quantifiers and alternating machines, conjecture it doesn’t collapse, time-space tradeoffs for SAT.
6. Circuits. ^[7] 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 ^[8] BPP, RP, coRP, ZPP. Examples of probabilistic algorithms. Error reduction via repetition. BPP in P/poly and PH. Randomized reductions, randomized logspace algorithms.
8. Complexity of Counting ^[9] #P. #P-completeness and Valiant’s theorem. Toda’s theorem.
9. Interactive Proofs ^[10] IP, AM. Graph non-isormorphism in AM. IP=PSPACE.
10. Cryptography ^[11] 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

11. Decision Trees ^[12] certificate complexity, randomized complexity, sorting lowerbounds
12. Communication Complexity ^[13] Lowerbound methods (fooling set, rank, tiling, discrepancy), multiparty communication complexity
13. Circuit lowerbounds. ^[14] Hastad switching lemma, lowerbounds for monotone circuits, frontier of circuit lowerbounds, approaches using communication complexity.
14. Algebraic complexity ^[15] Algebraic trees and circuits, Blum-Shub-Smale model.

Part III: Advanced Topics

15. Average Case Complexity: Levin’s Theory ^[16] DistNP and its complete problems.
16. Random and pseudorandom walks on graphs ^[17] second eigenvalue and analysis of random walks, expander graphs, zig-zag construction of expanders, reingold’s deterministic logspace algorithm for undirected connectivity.
17. Derandomization and Extractors ^[18] Pseudorandom generators from average-case hardness – the NW generators. Extractors from hash functions. Trevisan’s extractor from NW.
18. Hardness amplification and error correcting codes ^[19] Worst-case to average case reduction. Error correcting codes. Pseudoarndom generators from worst-case assumptions. List decoding and its use for hardness amplification.
19. PCP and hardness of approximation. ^[20] NP in PCP(poly,1). The PCP theorem (Dinur’s proof). Independent set is hard to approximate within a polynomial factor.
20. More PCP Theorems and the Fourier Transform Technique ^[21] 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)
21. Quantum Computation ^[22] Quantum computation and the class QBP. Shor’s factoring algorithm.
22. Logic in complexity theory ^[23] Proof complexity.
23. Why are circuit lower bounds so difficult? ^[24] Natural proofs.