University of Konstanz
Universität Konstanz
Fachbereich Informatik und Informationswissenschaft

"Complexity Theory" (Lecture and Tutorial)

Announcements

"Complexity theory is a central field of the theoretical foundations of computer science. It is concerned with the study of the intrinsic complexity of computational tasks. That is, a typical complexity-theoretic study looks at a task (or a class of tasks) and at the computational resources required to solve this task, rather than at a specific algorithm or algorithmic scheme. Actually, research in complexity theory tends to start with the computational resources themselves, and addresses the effect of limiting these resources on the class of tasks that can be solved. Thus, computational complexity is the study of the what can be achieved within limited time (and/or other limited natural computational resources)." (Oded Goldreich)

This course provides an introduction to the theory of computational complexity. It perfectly complements algorithmic studies. Topics include basic complexity measures and classes, space and time hierarchies, lower bounds, P versus NP, the polynomial hierarchy, alternations, probabilistic and counting complexity, circuits, interactive proof systems, and some selected problems of complexity theory.

Knowledge equivalent to an introductory course on theoretical computer science is required for this class.

General Information

Lectures (S. Kosub) Tuesday 17:00-18:30 (C 426)
Thursday 13:30-15:00 (D 430)
Tutorials (D. Weidele) Wednesday 17:00-18:30 (D 431)
Oral Exam 1st date: July 2015, TBA
2nd date: October 2015, TBA

Homework Assignments

No. Post Date Due Date Download

Content

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. Alternation
  8. Probabilistic computations
  9. Interactive proof systems

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 28 May 2015 v1.9 PDF

Literature

In-depth and background material of certain course aspects can be found in:
  1. Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge, 2009.
  2. Daniel P. Bovet, Pierluigi Crescenzi. Introduction to the Theory of Complexity. Prentice-Hall, Upper Saddle River, NJ, 1993.
  3. Mitsunori Ogihara, Lane A. Hemaspaandra. The Complexity Theory Companion. Springer-Verlag, Berlin, 2001.
  4. Christos H. Papadimitriou. Computational Complexity. Addision-Wesley, Reading, MA, 1994.
  5. 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

  1. This course in LSF
  2. Lecture notes Theoretische Grundlagen der Informatik (in German), Summer 2013.