The aim of the course is to make the student acquainted with the topics mentioned below, and to prepare him or her for more advanced topics in complexity theory.
After completing this course, the student should be able to classify problems in the various complexity classes, provide proofs of the main theorems, and perform constructions similar to the ones discussed during 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.
Topics:
- 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
- parameterized complexity
Prerequisites
Mathematical maturity commensurate with master's level, as well as a first course in mathematical logic, say as in the syllabus J. van Oosten and I. Moerdijk, Sets, Models, and Proofs, available on www.staff.science.uu.nl/~ooste110/syllabi/setsproofs17.pdf
In particular, acquaintance with propositional logic and first order predicate logic is required.
Rules about Homework / Exam
There will be a written exam at the end of the course.