Lectures (4 SWS/6 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
| Lectures: | Tuesday, 14:15-15:45, D 430 (Sven Kosub) |
| Thursday, 10:15-11:45, D 430 (Sven Kosub) | |
| Oral exams: | July 2011, TBA (1st date) |
| October 2011, TBA (2nd date) |
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
- The boolean hierarchy
- Alternation
- 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.
Literature
In-depth and background material of certain course aspects can be found in:
- 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, 2010.
- 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.