Strukturelle 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, dass 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. muss 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ße 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.

Inhalt

Die Vorlesung stellt eine Einführung in die Strukturelle Komplexität dar. Die dabei zentralen Fragen sind die folgenden:

  • Wie misst man sinnvoll den Aufwand, der nötig ist, ein Problem algorithmisch zu lösen?
  • Welche Ressourcen spielen dabei eine Rolle?
  • Wie lassen sich Probleme hinsichtlich dieser Ressourcen sinnvoll vergleichen und klassifizieren?
  • Was sind inhärente Hindernisse, die der Existenz beliebig guter Lösungen gewisser Probleme entgegen stehen?

Im Einzelnen werden u. a. folgende Gesichtspunke behandelt:

  • Turingmaschine, Zeit- und Platzverbrauch einer Rechnung
  • Komplexitätsklassen bzgl. Zeit- oder Platzbedarf
  • Hierarchiesätze, die Klassen P und NP als Formalisierung effizient lösbarer und effizient verifizierbarer Probleme
  • NP-Vollständigkeit, Reduktion
  • Satz von Cook: NP-Vollständigkeit von SAT
  • weitere Beispiele NP-vollständiger Probleme
  • Randomisierte Algorithmen und die Klassen ZPP, RP und BPP
  • Komplexitätsklassen innerhalb von P
  • Paralleles Rechnen und NC
  • Komplexitätsklassen jenseits von NP: die Polynomhierarchie, PSPACE und NSPACE, Zählklassen
  • Ausblicke auf andere Zugänge zu Komplexität

Zielgruppe

  •  4 SWS Vorlesung, 2 SWS Übung
  • 8 Kreditpunkte
  • Informatik Diplom/Bachelor Säule: Grundlagen der Informatik
  • Niveaustufe 400
  • Modul: 11449

Lernziele

Ziel dieser Lehrveranstaltung ist es, grundlegende Methoden zu erlernen mit deren Hilfe es möglich ist, Probleme gemäß der inhärenten Schwierigkeit bei ihrer algorithmischen Behandlung zu klassifizieren. Hierzu gehören:

  • das Kennenlernen sinnvoller Ressourcen zur Beurteilung der Komplexität eines Problems
  • das Verständnis für die grundlegende Struktur von Komplexitätsaussagen
  • das Beherrschen mathematischer Methoden zur Analyse und Klassifikation von Problemen
  • die selbständige Umsetzung der erlernten Methoden, um die Komplexität von Problemen richtig einzuschätzen.

Voraussetzungen

Die Kenntnis des Modells der Turingmaschine sowie der Begriffe Entscheidungsproblem und Berechenbarkeit wird empfohlen.
Zu Beginn der Vorlesung werden diese kurz wiederholt.

Literatur

  • S. Arora und B. Barak: Computational Complexity: A modern Approach, Cambridge, 2009. Eines der derzeit aktuellsten und auch besten Werke zum Thema. Es deckt die klassischen sowie die neueren Ergebnisse der Komplexitätstheorie umfassend ab.
  • C.Moore und S. Mertens: The Nature of Computing, Oxford University Press, 2011. Sehr umfangreiches neues Buch mit interessanten Teilen über Berechenbarkeit auch in anderen Modellen als der Turingmaschine.
  • 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.
  • Karl Rüdiger Reischuk: Komplexitätstheorie Band I: Grundlagen, Teubner 1999. Neufassung des vorstehenden Buches, deutlich erweitert.
  • (Karl Rüdiger Reischuk: Komplexitätstheorie Band II:Parallelität und Randomisierung. Erscheinung geplant 2007)
  • Michael R. Garey, David S. Johnson: Computers and Intractability, Freeman 1979. Eine große Sammlung an NP-vollständigen Problemen mit einer sehr ausführlichen 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.