Structural Complexity I: Basic Course

Lecture notes (in Russian):

These are lecture notes written mostly during Fall 2002 with later additions and corrections made during Fall 2004 and Fall 2006.

• defs.tex (alternatively, defsutf.tex) (you need this file if you need to compile .tex sources for some reason).
  
  
• Lecture 1: TeX source (and a picture), Postscript file, compressed Postscript file, PDF file.
  Search problems. Classes P and NP (of search problems). Reductions. NP-complete problems.
• Lecture 2: TeX source, Postscript file, compressed Postscript file, PDF file.
  Optimal algorithm for NP search problem. Languages that are neither NP-hard nor polynomial-time solvable. Tally and sparse sets.
• Lecture 3: TeX source, Postscript file, compressed Postscript file, PDF file.
  Deterministic space complexity. Languages with low space complexity. The space hierarchy theorem.
• Lecture 4: TeX source, Postscript file, compressed Postscript file, PDF file.
  Nondeterministic space complexity.
• Lecture 5: TeX source, Postscript file, compressed Postscript file, PDF file.
  Polynomial hierarchy.
• Lecture 6: TeX source, Postscript file, compressed Postscript file, PDF file.
  Randomized algorithms. Boolean circuits.
• Lecture 7: TeX source, Postscript file, compressed Postscript file, PDF file.
  IP=PSPACE. The Valiant-Vazirani lemma.
• Lecture 8: TeX source, Postscript file, compressed Postscript file, PDF file.
  Toda's theorem (the first part).
• Lecture 9: TeX source, Postscript file, compressed Postscript file, PDF file.
  Toda's theorem (the second part).
• Lecture 10: TeX source, Postscript file, compressed Postscript file, PDF file.
  Parallel computations.
• Lecture 11: TeX source, Postscript file, compressed Postscript file, PDF file.
  Probability amplification by random walks on expanders.
• Lecture 12 (NB: there is a slighly simpler newer proof by S.Aaronson): TeX source, Postscript file, compressed Postscript file, PDF file.
  Circuit complexity of polynomial hierarchy and PP.
• Lecture 13 (added on 21.12.2006): TeX source, Postscript file, compressed Postscript file, PDF file.
  Merlin-Arthur proofs are in ZPP^NP.
• Lecture 14 (added on 25.01.2007; not yet seen by the lecturer): TeX source, Postscript file, compressed Postscript file, PDF file.
  Time hierarchy for heuristic BPP.
• Lecture 15 (added on 9.01.2015): TeX source, PDF file.
  Reducing the number of rounds in Arthur-Merlin protocols.
• Lecture 16 (added on 10.02.2015): TeX source, PDF file.
  MIP=NEXP.

Literature:

• Oded Goldreich, Introduction to Complexity Theory. Lecture Notes, Weizmann Institute of Science, 1998-99.
• Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
• Lane A. Hemaspaandra, Mitsunori Ogihara, The Complexity Theory Companion, Springer, 2002. Two sample chapters are available electronically.
• Kitaev, Shen, Vyalyi (in Russian), Klassicheskie i kvantovye vychislenija, MTsNMO, 1999.

Further reading:

• Structural Complexity II: Advanced Course.