**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

- Docent: Sebastiaan Terwijn
- Docent: Markel Zubia