Type and Content

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)

• 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

• 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.

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.

Lecture

• Skript, Stand 8. Februar von Seite 1 bis Seite 76

Exercise

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

Arbeitsblätter für die Übung

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

• Vorbereitungsblatt für den 19. Oktober
• Vorbereitungsblatt für den 2. November
• Vorbereitungsblatt für den 5. Dezember