Brandenburgische Technische 
^{Universität Cottbus}

Startseite

Studium

Institut

BTU

John E. Hopcroft, Jeffrey D. Ullman:
Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Addison-Wesley 1994.
Trotz seines Alters (es stammt aus dem Jahr 1979) ein Bestseller wegen seines hervorragenden Stils - einer Mischung aus Anschaulichkeit und Präzision, die sehr gelungen ist. Für den Anfang ist dieses Buch zu empfehlen, auch wenn nicht sehr viel Komplexitätstheorie darin vorkommt.

José L. Balcázar, Josep Díaz, Joaquim Gabarró: Structural Complexity I+II,
Springer 1995.
Dies ist in einem ähnlich guten Stil geschrieben, überdeckt aber viel größere Bereiche der Theorie. Es ist sehr empfehlenswert

Wolfgang J. Paul: Komplexitätstheorie,
Teubner 1978
Der Autor ist brillant, das Buch alt und schnell geschrieben, zum Teil fordernd, aber umso lohnender.

Karl Rüdiger Reischuk: Einführung in die Komplexitätstheorie,
Teubner 1990.
Ein Buch, in dem man viel findet, sehr umfangreich an Stoff, wegen der starken Formalisierung nicht leicht zu lesen. Manchmal fehlen Beweise, die man auf Grund der Aufmachung erwartet, aber wer sich auf den Stil einläßt, kann viel lernen.

Michael R. Garey, David S. Johnson: Computers and Intractability,
Freeman 1979.
Eine große Sammlung an NP-vollständigen Problemen mit einer sehr ausfühlichen und leicht geschriebenen Einführung in die Problematik. Ein in der Szene sehr populäres Buch.

K. Wagner and G.Wechsung: Computational Complexity,
D.Reidel Publishing Company 1986.
Ein Kompendium, das sich zum Ziel gesetzt hat, die Ergebnisse der Theorie bis zum Erscheinungsjahr möglichst vollständig darzustellen. Trotz des gedrängten Stils sind meistens Beweise angegeben. Die augeklügelte vereinheitlichende Notation muß erst gelernt werden, bevor man es als Nachschlagewerk nützlich findet. Das Alter tut einer solchen Sammlung Abbruch, wenn man den heutigen Stand kennenlernen will, andererseits erkennt man daran, wie flüchtig die Ergebnisse der Informatik noch sind.

Zur Komplexitätstheorie

Für die Realisierung von Aufgaben ist der Aufwand an Zeit oder Speicher von nicht unerheblicher Bedeutung. Hierzu ist eine ganze Theorie entstanden, die sich mit der Komplexität von Aufgaben beschäftigt. Die Theorie der Komplexität besteht aus 3 unterschiedlichen, aber miteinander verwobenen Gebieten: Effiziente Algorithmen und ihre Analyse, Strukturelle Komplexitätstheorie und abstrakte Komplexitätstheorie.

Auf dem Gebiet der effizienten Algorithmen beschäftigt man sich damit, für definierte Probleme zeit- bzw. platzoptimale Algorithmen zu finden (obere Schranken), oder zu beweisen, daß es keine Algorithmen gibt, die weniger als einen vorgegebenen Aufwand treiben (untere Schranken). Dieses Gebiet ist der Praxis am nächsten, es ist voller zum Teil komplizierter Ideen, aber es gibt hier noch keine zusammenhängende Theorie mit Sätzen, die allgemein anwendbar sind.

Die strukturelle Komplexitätstheorie beschäftig sich mit Komplexitätsklassen, d.h. mit Gruppen von Aufgaben etwa gleicher Schwierigkeit. Kann man mit größerem Aufwand immer auch neue schwerere Aufgaben lösen oder gibt es Lücken, d.h. muß man mit dem Aufwand sehr viel höher gehen,  um neue Aufgaben lösen zu können? Gibt es einen Aufwand, mit dem man alle berechenbaren Aufgaben lösen kann? 

Eine besondere Rolle spielen die Aufgaben, die in einem vertretbaren Zeitaufwand lösbar sind, z.B., die höchstens einen polynomiellen Zeitbedarf haben. Um wieviel steigt der Aufwand, wenn wir einen nichtdeterministischen Algorithmus deterministisch simulieren wollen? Kann man die Aufgaben, die man nichtdetermistisch in polynomieller Zeit lösen kann (NP), auch deterministisch in polynomieller Zeit lösen (P)? Gibt es maximal schwere (NP-vollständige) Aufgaben in der Klasse NP, deren Zugehörigkeit zu P die Gleichheit von NP und P nach sich zöge?

Die abstrakte Komplexitätstheorie löst sich ganz von den konkreten Aufwandsmaßen und Modellen. Sie definiert axiomatisch, was ein Maß ist, und bildet daraus eine Theorie, die für alle Maß gilt, die konkreten, die man immer schon betrachtet wie Zeit und Platz, aber auch Maße, an die man zur Zeit noch nicht denkt. Diese Theorie ist noch klein und eher ein Gebiet der Rekursionstheorie.

Wir wollen uns hier mit der strukturellen Komplexitätstheorie befassen, d.h. die Struktur der Komplexitätsklassen untersuchen.