Curriculum M1 MPRI at ENS Paris-Saclay

Cours: Advances Complexity

Objectives : Complexity theory extends well beyond the concept of NP-completeness. The aim of this course is to examine a number of other fundamental constructs in complexity theory, such as space complexity and the concepts of alternating or randomized machines. We will explore some fascinating theorems, for instance, the equivalence between alternating time and deterministic space, or Shamir's IP=PSPACE theorem.

Summary:

  1. Deterministic and non-deterministic machines. Compression theorems.
  2. Non-deterministic space, NL, PSPACE, Savitch's theorem.
  3. Log-space reductions, NL-complete problems, NP-complete problems.
  4. Alternating machines, Kozen-Meyer-Stockmeyer theorems. Circuits, Horn clauses, and P-complete problems.
  5. Oracles. The polynomial hierarchy, the Boolean hierarchy.
  6. Counting problems, #P-completeness.
  7. Randomized Turing machines. The classes RP, coRP, ZPP.
  8. The class BPP. The class P/poly. Karp-Lipton and Adleman theorems.
  9. Jeux d'Arthur contre Merlin. Le théorème de Babai.
  10. Preuves interactives. Le théorème de Golwasser-Sipser. Le théorème de Boppana-Håstad-Zachos.
  11. Les classes ABPP et IP. Le théorème de Shamir.
  12. Une introduction aux problèmes d'approximation et à la classe PCP.

References

  • Lecture notes
  • Sylvain Perifel. Complexité algorithmique. Ellipses, 2014, 432 pages. isbn :978-2-729-88692-9.
  • Sanjeev Arora et Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. isbn : 978-0-521-42426-4

.