Kursinformation

Lehrinhalte
Komplexitätstheorie (Berechnungsmodelle, Reduzierbarkeit, Härte und Vollständigkeit, Approximierbarkeit, randomisierte Komplexität, parametrische Komplexitätstheorie)

Literatur
Sanjeev Arora, Boaz Barak: Computational Complexity, Cambridge University Press; Christos Papadimitriou: Computational Complexity, Pearson; Vijay Vazirani: Approximation Algorithms, Springer; Jörg Flum, Martin Grohe: Parameterized Complexity; Springer

Voraussetzungen
Lineare Algebra, „mathematische Reife“ (Teilnahme ohne Nachweis möglich)

Online-Angebote
moodle