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.