University of Konstanz
Universität Konstanz
Fachbereich Informatik und Informationswissenschaft

"Complexity Theory" (Lecture)


General Information

Lectures (S. Kosub) Tuesday 14:15-15:45 (D 430)
Thursday 10:15-11:45 (D 430)
Oral Exam 1st date: July 2011, TBA
2nd date: October 2011, TBA


The following topics are planned:

  1. Complexity measures and classes
  2. Complexity hierarchies
  3. Relations between space and time complexity
  4. Reductions and completeness
  5. Lower bounds
  6. The polynomial hierarchy
  7. The boolean hierarchy
  8. Alternation
  9. Probabilistic computations

Lecture Notes

Lecture notes are made available close in time to the lectures. The current version can be downloaded here. In case you have suggestions or comments (typos or any kind of errors) please send an email.

Chapter Date Version Download
All 2011/07/15 v0.12 PDF
Quiz 2011/06/07 PDF


In-depth and background material of certain course aspects can be found in:
  1. Daniel P. Bovet, Pierluigi Crescenzi. Introduction to the Theory of Complexity. Prentice-Hall, Upper Saddle River, NJ, 1993.
  2. Mitsunori Ogihara, Lane A. Hemaspaandra. The Complexity Theory Companion. Springer-Verlag, Berlin, 2010.
  3. Christos H. Papadimitriou. Computational Complexity. Addision-Wesley, Reading, MA, 1994.
  4. Gerd Wechsung. Vorlesungen zur Komplexitätstheorie. Teubner-Verlag, Stuttgart, 2000.
An online version of the Bovet-Crescenzi textbook is available as PDF under the Creative Commons Attribution-NonCommercial 2.5 License.

Further Information