Komplexitätstheorie

Prof. Dr.(USA) Martin Dietzfelbinger

Vorlesung: Montag, 13:00 - 14:30 Uhr
Raum: Hs 2

Auswertung Studierendenbefragung

Übungen (Prof. Dietzfelbinger, Dr. E. Hübel)

Übungsbeginn: 18.10.2006

Die letzte Aufgabe auf jedem Übungsblatt ist fakultativ und schwieriger. Lösungen zu diesen Aufgaben können schriftlich bei Prof. Dietzfelbinger eingereicht werden.

Inhalt

1. Die NP-Vollständigkeits-Theorie, in der Algorithmentheorie-Vorlesung begonnen, wird vertiefend behandelt: Der Satz von Cook/Levin wird bewiesen: SAT ist NP-vollständig. Viele weitere Probleme werden als NP-vollständig bzw. NP-schwer klassifiziert. Zentrales Thema: Reduktionen zwischen Problemen. Die Grenze zwischen P (effizient lösbar) und NP (wahrscheinlich nicht effizient lösbar) wird beleuchtet.
2. Approximationsalgorithmen und Nichtapproximierbarkeit: Manche Optimierungsprobleme lassen sich effizient lösen, wenn man mit fast optimalen Lösungen zufrieden ist. Dies ist ein attraktiver Ausweg, wenn das zu bearbeitende Problem NP-schwer ist. Manche Optimierungsprobleme lassen solche Approximationsalgorithmen nicht zu (z.B. das allgemeine TSP) oder nur begrenzt zu (Binpacking).
3. Randomisierte Algorithmen und ihre Komplexitätsklassen: Man betrachtet Algorithmen (und Turingmaschinen), die Zufallsexperimente ausführen. Diese Modellerweiterung führt zu weiteren Komplexitätsklassen.
4. „Interaktive Beweise“ – Ein Blick auf die PCP-Theorie und Nicht-Approximierbarkeit.
5. Polynomielle Hierarchie: Schwierige Probleme jenseits von NP.
6. Platzkomplexität, PSPACE-vollständige Probleme, Logspace-Reduzierbarkeit, P-Vollständigkeit.

Literatur

1. G. Ausiello et al., Complexity and Approximation, Springer, 1999.
2. K.-H. Niggl: Komplexitätstheorie, Materialien zur Vorlesung. WS 2005/06. http://www.tu-ilmenau.de/fakia/fileadmin/template/startIA/ktea/Lehre/kt/ws05/kt.pdf
3. M. Garey, D. Johnson, Computers and Intractability, W.H. Freeman and Co., 1979.
4. C. Papadimitriou, Computational Complexity, Addison-Wesley 1995.
5. I. Wegener, Komplexitätstheorie – Grenzen der Effizienz von Algorithmen, Springer, 2003.

    

   
   

Dokumente zur Vorlesung

Folien zur Vorlesung vom 06.11.2006 (Druckversion)

Folien zur Vorlesung vom 06.11.2006 (Blätterversion)

Folien zur Vorlesung vom 13.11.2006 (Druckversion)

Folien zur Vorlesung vom 13.11.2006 (Blätterversion)

Zur Vorlesung am 20.11.06: Illustration von Hamiltonkreisen

Zu 1.9: 3PM und BinPacking

Material zur Vorlesung am 22.01.2007: Analyse FPTAS für MAX RUCKSACK

Übungsblatt 1
Übungsblatt 2
Übungsblatt 3
Übungsblatt 4
Übungsblatt 5 Lösung von Aufgabe 5*
Übungsblatt 6 Lösung Aufgabe 3d
Übungsblatt 6-*Aufgabe
Übungsblatt 7
Übungsblatt 8
Übungsblatt 9
Übungsblatt 10
Übungsblatt 11
Übungsblatt 12
Übungsblatt 13
Übungsblatt 14

Sonderregelung zum Scheinerwerb (Stand 11.09.2006)