Komplexitätstheorie

Viele Konzepte der strukturellen Komplexitätstheorie stammen ursprünglich aus der Rekursionstheorie. Dort befasste man sich mit der Frage, welche Probleme überhaupt algorithmisch lösbar sind. Außerdem bemühte man sich, die unlösbaren Probleme zu klassifizieren. In der Komplexitätstheorie fragt man nun danach, welche Probleme mit vertretbarem Aufwand gelöst werden können. Dabei hat sich inzwischen die Übereinstimmung ergeben, dass ein Problem mit vertretbarem Aufwand gelöst werden kann, wenn es in polynomialer Rechenzeit gelöst werden kann. Dies führte zur Klasse P. Man bemühte sich nun, die Probleme zu klassifizieren, die nicht in P zu liegen scheinen. Bei diesen Untersuchungen hat man viele Konzepte aus der Rekursionstheorie auf den subrekursiven Bereich übertragen. Die dabei aufgetretenen Fragen und Probleme zählen vielfach zu den bedeutensten der (theoretischen) Informatik. Sie berühren unmittelbar unser Verständnis von dem, was algorithmisch mit vertretbarem Aufwand gelöst werden kann.

Die Vorlesung ist wie folgt aufgebaut:

Literatur:

J.L. Balcazar, J. Diaz, J. Gabborro:
Structural Complexity, I und II
EATCS Monographs on Theoretical Computer Science, Vol. 11 und 22, Springer, 1988.

Ergänzende Literatur:

R.V. Book:
Notes on Computational Complexity Theory
Skript, Fachbereich Informatik, Universität Kaiserslautern, 1984.
M.R. Garey, D.S. Johnson:
Computers and Intractability - A Guide to the Theory of NP-Completeness
Freeman, San Francisco, 1979.
J.E. Hopcraft, J.D. Ullman:
Introduction to Automata Theory, Languages and Computation
Addison-Wesley, 1979.
S.R. Mahaney:
Sparse Sets and Reducibilities
in: R.V. Book (ed.), Studies in Complexity Theory; Pitman, London, 1986.
W.J. Paul:
Komplexitaetstheorie
Teubner, 1978.
U. Schoening:
Complexity and Structure
Lecture Notes in Computer Science 211, Springer, 1985.
K. Wagner, G. Wechsung:
Computational Complexity
Reidel, 1986.