**Description** |
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 home of one of the most fundamental unsolved problems in mathematics, namely the question whether the class P is equal to NP or not. Possible topics that may be treated in the course are: time- and space-bounded computations, nondeterminism, reductions and completeness, relativized computation, diagonalization, the polynomial hierarchy, structure versus complexity of sets, randomization, circuit complexity, cryptography, proof complexity, interactive and zero-knowledge proofs. |