50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Komplexitätstheorie


Art und Inhalt

Titel: Komplexitätstheorie
Veranstalter: Nickelsen, Arpe
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)
Verlauf:
  • 18.10.06 Entscheidungs- und Konstruktionsprobleme, Zeit- und Platzklassen
  • 25.10.06 Hierarchiesatz für deterministischen Platz, Komposition von FL-Funktionen
  • 01.11.06 Komplementabschluss für Platzklassen
  • 08.11.06 Reduktionen: Many-One. Turing, Truth-Table
  • 15.11.06 Reduktionsabschluss von E ist EXP;
    PATH ist NL-vollständig, Reduktion PATH auf StronglyCONNECTED, Reduktion PATH auf AssoGENERABILITY
  • 22.11.06 Turingmaschinen und Schaltkreise;
    CVP ist P-vollständig, Reduktion CVP auf MCVP, Reduktion CVP auf Horn-SAT
  • 29.11.06 Circuit-SAT ist NP-vollständig, Reduktion Circuit-SAT auf 3-SAT; succinct-PATH ist PSPACE-vollständig;
    Approximation, Algorithmus für Max-3-SAT
  • 06.12.06 Approximationsklassen, Algorithmus für MinTSP, Trennende Probleme für Approximationsklassen
  • 13.12.06 Algorithmus für MaxKNAPSACK
    Probabilistische TM
  • 20.12.06 Probabilistische Klassen, Inklusionen, exponentiell kleiner Fehler
  • ---------------- Weihnachtspause ----------------
  • 10.01.07 P/poly, BPP in P/poly, Teilinformationsalgorithmen
  • 17.01.07 P-Selektive Sprachen in P/poly, Selbstreduzierbarkeit
  • 24.01.07 Polynomielle Hierarchie, PH und PSPACE
  • 31.01.07 Polynomielle Hierarchie, Quantoren-Charakterisierung
  • 07.02.07 BPP in PH; Rückblick und Beweismethoden
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.
Scheinerwerb, Note:

Für den Scheinerwerb muss man die mündliche Prüfung (Do, 15. Februar) am Ende des Semesters bestehen und bei den Aufgabenblättern die Hälfte der möglichen Punktzahl erreichen. Bei benoteten Scheinen gehen die Note der mündlichen Prüfung und die Note aus den Aufgabenblättern zu gleichen Teilen in die Gesamtnote ein.

Vorlesung

Veranstalter: Nickelsen
Umfang: 2 SWS, 4 ECTS
Termine: Mi, 12.30 Uhr – 14.00 Uhr, ITCS Seminarraum (Raum 21)
Beginn: 18. Oktober
Skript: Im Laufe des Semesters werden hier Skriptteile zu den einzelnen Teilen der Vorlesung bereitgestellt.

Übung

Umfang: 1 SWS
Termine: Do, 10.15 Uhr – 12.00 Uhr, ITCS Seminarraum (Raum 21)
Beginn: 19. Oktober
Übungsunterlagen:

In der wöchentlichen Übung werden Fragen zum Vorlesungsinhalt und den Aufgabenblättern besprochen. Es ist geplant, im Laufe des Semesters etwa 10 Aufgabenblätter herauszugeben. Die Lösungen werden jeweils in der folgenden Woche in der Übung abgegeben. Die Lösungen werden mit Punkten bewertet.

Im Laufe des Semesters werden hier die Aufgabenblätter veröffentlicht.

Aufgabenblätter

Blatt Ausgabe Abgabe Thema
Blatt 1 18.10. 26.10. Entscheidungs- und Berechnungsproblem, NL, FL
Blatt 2 25.10. 02.11. MAJ-SAT, NTM-Acceptance, (Logspace-)Komposition
Blatt 3 31.10. 09.11. Anwendungen von Immerman-Szelepcsenyi
Blatt 4 08.11. 16.11. Turing- und Truth-Table-Reduktionen (UniqueSat)
Blatt 5 15.11. 23.11. Reduktionsabschluss von DSPACE(n); Beispiele Reduktionen (Erreichbarkeit)
Blatt 6 22.11. 30.11. Generability ist P-vollständig; Zusatzaufgabe: Reduzierbarkeit bildet Quasiordnung mit Suprema
Blatt 7 29.11. 07.12. Vollständige Sprachen für DTIME(n); Optimierungsproblem Max-3-SP
Blatt 8 06.12. 21.12. Approximationsalgorithmen für Min-Vertex-Cover
Blatt 9 10.1. 18.1. Turingabschluss von BPP; p-Selektivität; Zusatzaufgabe: Hierarchiesatz für Adviceklassen
Blatt 10 17.1. 25.1. Selbstreduzierbarkeit und Teilinformationsklassen
Blatt 11 24.1. 1.2. Nur Zusatzaufgaben: Polynomielle Hierarchie und Gemischtes

Arbeitsblätter für die Übung

Für manche Übungstermine gibt es zusätzliche Arbeitsblätter: