LFU:online

Absolvent:innen dieses Moduls haben ein Verständnis dafür, wie Zeit- und Platzbedarf von Entscheidungsproblemen formal definiert werden können. Sie kennen die grundlegenden Komplexitätsklassen (P, NP, coNP, PSPACE, etc.) und wie sie zueinander in Zusammenhang stehen und warum. Sie kennen ebenfalls einige wichtige Fragen hierzu, die noch offen sind. Sie kennen repräsentative Probleme für jede Klasse und sind in der Lage, zu argumentieren, warum ein Problem in einer bestimmten Klasse ist oder vollständig für diese Klasse ist.

Berechnungsmodelle; Zeit- und Platzbedarf von Turingmaschinen; Berechnungen in polynomieller Zeit (P, NP, coNP); NP-Vollständigkeit (SAT, 3-SAT, Karps Probleme, Satz von Cook–Levin); Platzklassen und der Satz von Savitch; PSPACE, TQBF, die polynomielle Hierarchie, Alternierung; logarithmische Platzklassen (L und NL); Hierarchiesätze; ausgewählte fortgeschrittene Themen (z.B. Schaltkreiskomplexität, Orakel und Relativisierung, probabilistische Klassen, interaktive Beweise)

In der Vorlesung: Präsentation mit Folien und Tafel. Der Kurs orientiert sich stark an zwei Lehrbüchern (siehe Webseite).

In der Übung: Wöchentliche Hausübungen, deren Lösungen zusammen in der Übung diskutiert werden.

M. Sipser, Introduction to the Theory of Computation, 2014.
S. Arora & B. Barak, Computational Complexity: A Modern Approach, 2007.
D. C. Kozen, Theory of Computation, 2006.

Die Module ‘Einführung in die Theoretische Mathematik’ und ‘Diskrete Strukturen’ müssen bestanden sein. Zusätzlich ist es empfehlenswert (wenn auch nicht zwingend notwendig), die ‘Logik’-Vorlesung besucht zu haben.

Insbesondere sollten Student:innen die folgenden Fähigkeiten/das folgende Wissen aufweisen, um in der Vorlesung gut zurechtzukommen:

• Gutes Verständnis von mathematischer Notation, Fähigkeit zum mathematischen Denken, etc.
• Gutes Verständnis grundlegender diskreter Mathematik (weiß, was eine Relation ist, hat schon einmal von Graphfärbung gehört, etc.)
• Vertrautheit mit Aussagenlogik und Prädikatenlogik
• Turingmaschinen
• Kenntnisse über formale Sprachen, Automaten, reguläre Ausdrücke können nützlich sein.