Complexity Theory

Credits 8 credit points
Instructors Pietrzak, K. (CWI), Terwijn, S.A. (Radboud Universiteit Nijmegen)
Prerequisites No specific knowledge is required, except for some mathematical maturity. Some acquaintance with mathematical logic (propositional logic and predicate logic) is helpful.
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.

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,
the polynomial hierarchy,
structure versus complexity of sets,
circuit complexity,
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.

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
Remarks More information you can find here.
  Last changed: 05-03-2015 16:29