(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
Panorama der Komplexitätstheorie via Graph Ramsey Spielen
Grundlagen (Kapitel 1 und 2 aus Papadimitriou, Computational
Complexity, 1994)
Turing Maschinen, linear speedup, Random Access Maschinen,
Nichtdeterministische Turing Maschinen, NP-Vollständigkeit,
Cook's Beweis
Reduktionen (3CNF, MAX2SAT, CLIQUE), HORNSAT
Weitere Reduktionen (Independent Set, Vertex Cover, Subset
Sum, Rucksack, Gerichteter Hamiltonscher Kreis, Ungerichteter
Hamiltonscher Kreis, TSP)
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)
Komplexitätsklassen P, NP, PSPACE, EXP, L, NL; Komplementäre Klassen;
Hierarchie Theoreme, Gap Theorem
Erreichbarkeitsmethode, Beziehungen zwischen den Komplexitätsklassen P, NP, PSPACE, EXP, L, NL; Savitchs Theorem
Immerman-Szelepscényis Theorem, NL=coNL
Kolmogorov Komplexität, universelle Wahrscheinlichkeitsverteilung, average case vs. worst case, untere Schranken mittels Kolmogorov Komplexität
Interaktive Beweise, Zero Knowledge Beweise
Parameterisierte Komplexitätstheorie: Das Data Cleaning
Problem, Vertex Cover ist FPT, parameterisierte Transformationen und
Komplexitätsklassen
Weitere mögliche Themen:
- PSPACE
- Quantencomputer
- Kryptographie und Protokolle
- Randomisierte Komplexitätstheorie
- Entscheidbarkeit
- Zählkomplexitätstheorie
- ...
Wolfgang Slany
Last modified: 2003-3-4 12:26 CET