Complexity course at the Jagiellonian University
Algorithmics Research Group
May and June 2007
Michael Soltys
List of topics:
1) Turing machines and a lower bound for palindromes using rudimentary
Kolmogorov complexity.
2) P and NP, Cook's theorem and NP-completeness, "self-reducibility"
of SAT, and the padding argument to relate, for example, the collapse
of P and NP to the collapse of EXP and NEXP.
3) Space complexity, the logarithmic classes L and NL, and Reingold's
recent result showing that L=SL. Savitch's theorem and
PSPACE=NPSPACE, and the Immerman-Szelepscenyi theorem showing that
NL=co-NL. Interactive proof systems: IP.
4) Diagonalization and oracles, and the hierarchy theorems. The
polynomial time hierarchy (PH), and the linear time hierarchy (LTH),
and the Nepomnjascij's theorem.
5) Circuits, a lower bound for parity (showing that it cannot be
computed with bounded depth circuits of polynomial size), and an
alternative proof of the same result using the technique of
arithmetization. Shannon's result about boolean circuits, and
Razborov's result showing a lower bound for monotone circuits.
Razborov-Smolensky result about circuits with modular gates.
6) Proof systems, especially resolution, and relation to the DPLL and
DP algorithms. Haken's lower bound for resolution, as well as
automatizability and interpolation. Mention Frege proof systems, and
the open problems in the area.
7) Randomized complexity classes: examples of randomized algorithms
for perfect matching, primality testing, and pattern matching. The
classes RP, co-RP, ZPP, BPP, and counting classes such as PP, #P, and
+P. Chernoff bound and amplification. The isolation lemma and Toda's
theorem, and computation with advice, in particular the result of
Allender et al showing that NL/poly=UL/poly.