50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Komplexitätstheorie - CS4003


Art und Inhalt

Titel: Komplexitätstheorie
Veranstalter: Tantau
Einordnung: Diplom-Studiengang ab 5. Semester, Vertiefung Theoretische Informatik
Master-Studiengang Computational Life Science, 1. Semester, Wahlpflichtmodul Vertiefung Informatik
Master-Studiengang Informatik ab 2. Semester, Wahlplichtmodul Grundlagen der Informatik
Inhalt:

Die Komplexitätstheorie klassifiziert algorithmische Probleme nach ihrem Berechnungsaufwand. Typische Aufwandsmaße sind Laufzeit und Speicherplatz. Die Probleme werden nach ihren Aufwandsschranken zu Komplexitätsklassen zusammengefasst.

Die bekanntesten Klassen sind P und NP (polynomielle Laufzeit) und PSPACE (polynomieller Platz). Betrachtet man auch andere Algorithmenarten wie probabilistische Algorithmen oder Approximationsalgorithmen, so ergeben sich weitere Qualitätsmaße und damit weitere Komplexitätsklassen.

Die Komplexitätstheorie versucht Ordnung in diesen "Zoo" von Komplexitätsklassen zu bringen.

Inbesondere wird untersucht:

  1. Welche strukturellen Eigenschaften hat eine Klasse (zum Beispiel Abgeschlossenheit unter Reduktion)?
  2. Gibt es Probleme maximaler Schwierigkeit in der Klasse (vollständige Probleme)?
  3. Welche Inklusionen bestehen zwischen verschiedenen Komplexitätsklassen (gibt es zum Beispiel für jedes Problem in NP einen schnellen probabilistischen Algorithmus)?
  4. Wie kann man Probleme, die schwierig sind (z.B. NP-vollständig), trotzdem sinnvoll algorithmisch behandeln (etwa mit Näherungs-, probabilistischen oder Fixed-Parameter-Algorithmen)?

Folgende Themen werden in der Vorlesung behandelt:

  1. Abschlusseigenschaften von Platzklassen (Satz von Immerman-Szelepcsényi)
  2. Reduktionen (Many-One, Turing, Truth-Table)
  3. Vollständige Probleme für NP, P, PSPACE, NL
  4. Approximationsalgorithmen für NP-vollständige Probleme (z.B. für TSP)
  5. probabilistische Algorithmen
  6. Teilinformationsalgorithmen (P-Selektivität)
  7. Die Polynomielle Hierarchie zwischen NP und PSPACE
  8. Fixed-Parameter-Algorithmen (z.B. für Vertex Cover)
Buchempfehlungen:
  • Ch. Papadimitriou; Computational Complexity, Addison Wesley, 1994.
  • M. Garey, D. Johnson; Computers and Intractability, Freeman & Co., 1979.
  • R. Reischuk; Einführung in die Komplexitätstheorie (2. Auflage), Teubner, 1999.
Wiki Wiki zur Veranstaltung

Vorlesung

Veranstalter: Tantau
Umfang: 2 SWS, 4 ECTS
Termine: Mi, 10:00 Uhr – 12.00 Uhr, R3

Übung

Veranstalter: Tunjic
Umfang: 1 SWS
Termine: Mo, 16:00 Uhr – 18:00 Uhr, AM S2