Course info

Prerequisites
A first course in mathematical logic, comparable to the material in the book
J. van Oosten and I. Moerdijk, Sets, Models, and Proofs.
In particular, acquaintance with propositional logic and first order predicate logic
is required. Furthermore, we will use basic concepts from graph theory and probability
theory.

Aim of the course
Complexity theory is a field on the border of mathematics and computer science, where computational
problems are classified according to the resources (such as computation time and space) that are
needed to solve them. This leads to a number of fundamental complexity classes such as P, NP, PSPACE
and many others. These classes serve as benchmarks for the difficulty of computational problems, and
have numerous applications in mathematics as well as in other fields. This area is also the home of
one of the most fundamental unsolved problems in mathematics, namely the question whether the classes
P and NP are equal or not.

The goal of the course is to make the student acquainted with the topics mentioned
below and to prepare the student for more advanced topics in complexity theory.

• Time- and space-bounded computations
• nondeterminism
• basic complexity classes, P, NP, PSPACE, EXP
• reductions and completeness
• relativized computation
• diagonalization
• the polynomial hierarchy
• structure versus complexity of sets
• randomization, PP, BPP
• cryptography
• circuit complexity and nonuniform computation
• proof complexity
• interactive and zero-knowledge proofs

At the end of the course the student should be able to

- classify problems in various complexity classes
- build reductions and give completeness proofs for NP and other complexity classes
- perform diagonalization constructions similar to the ones discussed during the course
- classify problems in the polynomial hierarchy
- reason about randomized computation
- prove results about circuit complexity
- handle protocols for various interactive proofs

Lecturers
Sebastiaan Terwijn