Computational Complexity - Summer 2022

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 master's 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/counting complexity, and fundamentals of quantum complexity.

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

Times

Homework Assignments

Assignments are made available in ILIAS every Friday. The editing time for each homework is about one week. It is due on the next Friday at 12:00 via Upload in ILIAS. The assignments have to be delivered in written form in English. The corrected and scored assignments will be returned and discussed in the next tutorial.

You are allowed and encouraged to work in groups of two.

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
• Counting classes
• Quantum computational complexity

Lecture Notes

Lecture notes are made available in ILIAS close in time to the lectures. 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.