What is complexity theory

Complexity theory

Speaker: Prof. Carsten Lutz

K4, module area theory

Tue 17-19 MZH 7250
Thu 15-17 MZH 7250

Examination date: 9.9.2009. Please arrange specific dates by email.

Brief description

The complexity theory deals with the inherent Computational problem complexity: how much time (or other resources) does it take to solve a given problem — regardless of how clever the algorithm you are using? So it's about the limits of predictability under limited resources. Complexity theory thus represents an important basis for the design and understanding of efficient algorithms. It also tries to satisfy the natural curiosity for what is feasible in principle in computer science. The lecture will deal with the following topics:
  • Basic terms such as reductions, hardness and completeness
  • The P vs. NP problem and its variations
  • NP-complete problems from different branches of computer science
  • Hierarchy theorems and related results
  • Space complexity classes such as PSpace and LogSpace
  • Circuit complexity and efficient parallelization
  • The polynomial hierarchy
  • Probabilistic complexity classes




  • Oded Goldreich. Computational Complexity: a Conceptual Perspective. Cambridge University Press, 2008.
  • Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
  • Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
  • Ingo Wegener. Complexity Theory - Limits to the Efficiency of Algorithms. Springer, 2003.
  • Michael Sipser. Introduction to the Theory of Computation (2nd Edition). Thomson Course Technology, 2006

Working group theory of artificial intelligence