Mitteilungen

Der Übungsbetrieb beginnt in der 15. Kalenderwoche

Termine

Die NP-Vollständigkeits-Theorie, in der Vorlesung "Berechenbarkeit und Komplexität" 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.
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).
Randomisierte Algorithmen und ihre Komplexitätsklassen: Man betrachtet Algorithmen (und Turingmaschinen), die Zufallsexperimente ausführen. Diese Modellerweiterung führt zu weiteren Komplexitätsklassen. Auch realistischerweise muss schnelle randomisierte Algorithmen als "effizient" ansehen und kommt damit (eventuell) über P hinaus.
„Interaktive Beweise“ – Ein Blick auf die PCP-Theorie und Nicht-Approximierbarkeit.
Polynomielle Hierarchie: Schwierige Probleme jenseits von NP.
Platzkomplexität, PSPACE-vollständige Probleme, Logspace-Reduzierbarkeit, P-Vollständigkeit.

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