50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Komplexitätstheorie - CS4003


Type and Content

Title: Komplexitätstheorie
Lecturer: Prof. Dr. Till Tantau
Classification: Master-Studiengang Informatik 2. Semester, Anwendungsfach IT-Sicherheit und Zuverlässigkeit
Master-Studiengang Informatik 2. Semester, Wahlplichtmodul Grundlagen der Informatik
Content:

Die Komplexitätstheorie klassifiziert algorithmische Probleme nach ihrem Berechnungsaufwand. Typische Aufwandsmaße sind Laufzeit und Speicherplatz. Die Probleme werden nach ihren Aufwand 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 und vollständige Probleme
  2. Reduktionen (Many-One, Turing, Truth-Table), relativierte Komplexität
  3. Approximationsalgorithmen für NP-vollständige Probleme (z.B. für TSP)
  4. probabilistische Komplexitätsklassen
  5. Die Polynomielle Hierarchie zwischen NP und PSPACE
Literature:
  • S. Arora, B. Barak, Computational Complexity, Cambridge Univ. Press, 2009
  • B. Cooper: Computability Theory - Chapman & Hall, 2004
  • D. Kozen: Theory of Computation - Springer, 2006
  • R. Reischuk; Einführung in die Komplexitätstheorie (2. Auflage), Teubner, 1999.

Lecture

Lecturer: Prof. Dr. Till Tantau
Hours: 2 SWS, 4 ECTS
Dates: Di, 10:00 Uhr – 12.00 Uhr, Seminarraum ITCS 2021, erste Vorlesung ist am 16.4.14 (Mittwoch) von 14-16 Uhr im ITCS Seminarraum 2021.

Exercise

Lecturer: M.Sc.Benito van der Zander
Hours: 2 SWS
Dates: Mi, 14:00 Uhr – 16:00 Uhr, ITCS 2021, ab 16.4 bzw. 23.4 im ITCS 2021