2nd semester 
20 credits / 30 lectures

This module, which is geared towards students in both Mathematics and Computer Science, provides an introduction to major topics in computational complexity theory, which is one of the core areas of theoretical computer science. In computational complexity, we investigate the power of efficient computation. That is, we try to distinguish between computational problems that can be solved efficiently in practice and those that, though theoretically solvable, are not solvable in practice because of prohibitively large time or space requirements. The central open problem is the P versus NP problem.

• Nondeterministic and deterministic Turing machines
• Basic time and space complexity classes
• Space and time hierarchies
• NP and NP-completeness
• The polynomial hierarchy
• Oracle complexity classes
• Relativisation of the P versus NP problem
• Space-bounded computation
• Probabilistic algorithms
• Boolean circuits
• Counting problems
• Interactive proof systems