Complexity Theory - Winter 2016

Lectures and Tutorials (6 SWS/9 ECTS)

„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.

Times 

Homework Assignments

Assignments are made available on this webpage as a PDF-file (in English) every Wednesday. The editing time for each homework is about one week. It is due on the next Wednesday at 17:00 (right before the start of the tutorial). The assignments have to be delivered in written form in English. The corrected and scored assignments will be returned in the next tutorial.

Content

The following topics are planned:

• Complexity measures and classes
• Complexity hierarchies
• Relations between space and time complexity
• Reductions and completeness
• Lower bounds
• The polynomial hierarchy
• Alternation
• Probabilistic computations
• 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.

Literature

In-depth and background material of certain course aspects can be found in:

• Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge, 2009.
• Daniel P. Bovet, Pierluigi Crescenzi. Introduction to the Theory of Complexity. Prentice-Hall, Upper Saddle River, NJ, 1993.
• Mitsunori Ogihara, Lane A. Hemaspaandra. The Complexity Theory Companion. Springer-Verlag, Berlin, 2001.
• Christos H. Papadimitriou. Computational Complexity. Addision-Wesley, Reading, MA, 1994.
• 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.