Komplexitätstheorie

(181.142 VU SS 2,0).

Sommersemester 2003: Die Vorlesung entfällt dieses Semester.

Bitte über SIDES-4mi zur Vorlesung anmelden!


Übersicht über die Vorlesungseinheiten

  1. Panorama der Komplexitätstheorie via Graph Ramsey Spielen

  2. Grundlagen (Kapitel 1 und 2 aus Papadimitriou, Computational Complexity, 1994)

  3. Turing Maschinen, linear speedup, Random Access Maschinen, Nichtdeterministische Turing Maschinen, NP-Vollständigkeit, Cook's Beweis

  4. Reduktionen (3CNF, MAX2SAT, CLIQUE), HORNSAT

  5. Weitere Reduktionen (Independent Set, Vertex Cover, Subset Sum, Rucksack, Gerichteter Hamiltonscher Kreis, Ungerichteter Hamiltonscher Kreis, TSP)

  6. Approximier- und Nichtapproximierbarkeit von NP Problemen, Komplexitätsklassen NPO, PO, APX, PTAS, FPTAS, das PCP Theorem, Beispielprobleme (Shortest Path, Minimum Vertex Cover, TSP, Rucksack, MAX3CNF)

  7. Komplexitätsklassen P, NP, PSPACE, EXP, L, NL; Komplementäre Klassen; Hierarchie Theoreme, Gap Theorem

  8. Erreichbarkeitsmethode, Beziehungen zwischen den Komplexitätsklassen P, NP, PSPACE, EXP, L, NL; Savitchs Theorem

  9. Immerman-Szelepscényis Theorem, NL=coNL

  10. Kolmogorov Komplexität, universelle Wahrscheinlichkeitsverteilung, average case vs. worst case, untere Schranken mittels Kolmogorov Komplexität

  11. Interaktive Beweise, Zero Knowledge Beweise

  12. Parameterisierte Komplexitätstheorie: Das Data Cleaning Problem, Vertex Cover ist FPT, parameterisierte Transformationen und Komplexitätsklassen

Weitere mögliche Themen:


Wolfgang Slany
Last modified: 2003-3-4 12:26 CET