LFU:online

Graduates understand how to formally measure the time and space usage of computer programs. They are familiar with basic complexity classes (P, NP, coNP, PSPACE, etc.) and how they relate to one another and why. Furthermore, they are aware of some important questions about them that are still open. They know some representative problems for each class and have the ability to argue that some particular problem is an element of a class or is complete for a class.

Computational models; measuring time and space usage of Turing machines; polynomial-time computation (P, NP, coNP); NP-completeness (SAT, 3-SAT, Karp's problems, Cook–Levin Theorem); space complexity and Savitch's theorem; PSPACE, TQBF, the Polynomial Hierarchy, alternation; logarithmic space classes (L and NL); hierarchy theorems; selected advanced topics (e.g. circuit complexity, oracles and relativisation, probabilistic classes, interactive proofs)

Presentation with slides and blackboard. The course closely follows one or two textbooks (see website).
Weekly homework exercises whose solutions are discussed together.

Weighted average of weekly homework submission and a written exam. No repeat exam will be offered.

M. Sipser, Introduction to the Theory of Computation, 2014.
S. Arora & B. Barak, Computational Complexity: A Modern Approach, 2007.
D. C. Kozen, Theory of Computation, 2006.

Must have passed ‘Introduction to Theoretical Computer Science’ (ETI) and ‘Discrete Structures’. Having attended the ‘Logic’ course is recommended, but not required.

In particular, students should have the following skills/knowledge to do well in the lecture:

• being comfortable with formal mathematical notation, mathematical thinking, etc
• good familiarity with basic discrete mathematics (knows what a relation is, what a graph colouring is, etc.)
• familiarity with propositional and first-order logic
• Turing machines
• some knowledge of formal languages, automata, regular expressions can be useful.