Komplexitätstheorie (WiSe 2012/2013)

Eintrag im LSF

Inhalt

Die Komplexitätstheorie versucht, algorithmische Probleme im Hinblick auf ihre Schwierigkeit anhand der für ihre Lösung inhärent (also unabhängig von einem konkreten Algorithmus) notwendigen Resourcen wie Rechenzeit und Speicherbedarf zu klassifizieren. Die berühmteste offene Frage der Komplexitätstheorie ist sicherlich, ob die Klasse P der Entscheidungsprobleme, für die man in polynomial beschränkter Zeit berechnen kann, ob die Antwort Ja oder Nein ist, gleich der Klasse NP der Entscheidungsprobleme ist, für die man, falls die Antwort Ja ist, dies in polynomial beschränkter Zeit nachweisen kann. Nachdem wir die mathematischen Grundlagen der Komplexitätsheorie gelegt und die Klassen P, NP, und coNP genauer beleuchtet haben, werden wir Themen wie die polynomielle Hierarchie, Boole'sche Schaltkreise, randomisierte Algorithmen, Kryptographie, Quanten-Algorithmen und die Theorie der probabilistisch überprüfbaren Beweise betrachten, welche in der jüngeren Vergangenheit zu erheblich vertieftem Verständnis der Komplexität schwieriger Optimierungsprobleme geführt hat.

Termine

Vorlesung (Jun.-Prof. G. Averkov & Prof. V. Kaibel)

Übung (Jun.-Prof. G. Averkov)

(Campus-Plan)

Übungsblätter

Literatur