Complexity Theory

Credits	8 credit points
Instructors	Pietrzak, K. (CWI), Terwijn, S.A. (Radboud Universiteit Nijmegen)
E-mail	pietrzak@cwi.nl, terwijn@math.ru.nl
Aim	To get the student acquainted with the basic results and notions of complexity theory, as well as to give an idea of various more advanced directions of research.
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.
Organization	Each meeting consists of three times 45 minutes, the first two of which will be used for lectures and the last for the discussion of exercises.
Examination	Written exam on June 14, 2011. 13:00-16:00 room C0.110, Science Park.
Literature	− A syllabus and other possible handouts will be made available during the course. − S. Arora and B. Barak, Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Drafts of the book are available online at www.cs.princeton.edu/theory/complexity/
Prerequisites	No specific knowledge is required, except for some mathematical maturity. Some acquaintance with mathematical logic (propositional logic and predicate logic) is helpful.
Remarks	More information you can find here.

Last changed: 07-05-2013 16:59