# 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 ZPPNP.
• 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: