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. NPcomplete problems.
 Lecture 2:
TeX source,
Postscript file,
compressed Postscript file,
PDF file.
Optimal algorithm for NP search problem.
Languages that are neither NPhard nor polynomialtime 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 ValiantVazirani 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.
MerlinArthur 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 ArthurMerlin 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, 199899.

Christos H. Papadimitriou, Computational Complexity, AddisonWesley, 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:
Back to Home Page