Vorlesung: Komplexitätstheorie

Dozent: Olaf Beyersdorff

Termine:	`VL Mo 11-13 (RUD 25, 4.101) O. Beyersdorff`
	`VL Mi 15-17 (RUD 25, 4.101) O. Beyersdorff` `UE Mo 13-15 (RUD 25, 4.101) L. Weizsaecker`

Zuordnung:	Hauptstudium, Halbkurs

Inhalte und Lernziele

Welcher Aufwand ist nötig, um ein ein algorithmisches Problem (man denke etwa an das Traveling Salesman Problem) auf einem Computer zu lösen? Sobald man einen korrekt arbeitenden Algorithmus gefunden hat, stellt sich die Frage, ob die von diesem Algorithmus beanspruchten Ressourcen - in erster Linie Rechenzeit und Speicherplatz - auch tatsächlich nötig sind. Hierzu muss man nachweisen, dass es keinen wesentlich effizienteren Algorithmus für dieses Problem gibt. Für die weitaus meisten Problemstellungen (das Traveling Salesman Problem bildet hierbei keine Ausnahme) ist diese Frage trotz intensiver Forschung bis heute offen.

Um derartige Fragestellungen präzise formulieren (und nach einer Antwort suchen) zu können, werden reale Rechenmaschinen durch mathematische Modelle nachgebildet. Dabei ist man nicht nur an gegenwärtigen sondern auch an zukünftigen Technologien (etwa zur Parallelverarbeitung) interessiert. Auf der Basis dieser Modelle lassen sich durch eine Beschränkung der zur Verfügung stehenden Ressourcen so genannte Komplexitätsklassen bilden, in die die bekannten algorithmischen Problemstellungen nach ihrem Bedarf an Rechenressourcen eingeordnet werden können (die Komplexität des Traveling Salesman Problems ist beispielsweise durch die Klasse NP charakterisiert).

Für die meisten in der Praxis relevanten Problemstellungen lässt sich die Frage, ob es wesentlich effizientere Algorithmen als die bisher bekannten gibt, darauf zurückführen, ob bestimmte Komplexitätsklassen wie etwa P und NP gleich sind oder nicht (P-NP-Problem). Welche Beziehungen zwischen den unterschiedlichen Komplexitätsklassen bestehen, ist daher ein zentrales Forschungsthema der Theoretischen Informatik. Aus dem Inhalt der VL:

Berechnungsmodelle, Platz- und Zeitkomplexität
Probabilistische Algorithmen, Beziehungen zwischen verschiedenen Komplexitätsklassen
Reduktionen, NP-Vollständigkeit und das P-NP-Problem
Klassifikation konkreter Entscheidungs-, Such-, Optimierungs- und Anzahlprobleme
Bewältigung harter Probleme (approximative und heuristische Lösungsansätze)
Logische Charakterisierung von Komplexitätsklassen
Interaktive Beweissysteme
Kombinatorische Schaltkreise und parallele Komplexitätsklassen

Literatur

M.R. Garey, D.S. Johnson. Computers and Intractability - A Guide to the Theory of NP-Completeness. Freeman, 1979.
L.A. Hemaspaandra, M. Ogihara. The Complexity Theory Companion. Springer, 2001.
S. Homer, A.L. Selman. Computability and Complexity Theory. Springer, 2001.
J.E. Hopcroft, R. Motwani, J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 2001.
H.R. Lewis, C.H. Papadimitriou. Elements of the Theory of Computation. Prentice-Hall, 1998.
R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
K.R. Reischuk. Komplexitätstheorie, Band I: Grundlagen. Teubner, 1999.
U. Schöning. Perlen der Theoretischen Informatik. BI-Wissenschaftsverlag, 1995.
U. Schöning. Theoretische Informatik, kurz gefaßt. Spektrum Akademischer Verlag, 1997.
M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
K.W. Wagner. Einführung in die Theoretische Informatik. Springer, 1994.
G. Wechsung. Vorlesungen zur Komplexitätstheorie. Teubner, 2000.
I. Wegener. Theoretische Informatik. Teubner, 1993.
I. Wegener. Kompendium Theoretische Informatik. Eine Ideensammlung. Teubner, 1996.

Aufgabenblätter

Ben Bäßler