Vorlesung + Übung: Computational Complexity - Details

Allgemeine Informationen

Veranstaltungsname	Vorlesung + Übung: Computational Complexity
Veranstaltungsnummer	W 1247
Semester	WS 2026/27
Aktuelle Anzahl der Teilnehmenden	5
Heimateinrichtung	Institut für Informatik
Veranstaltungstyp	Vorlesung + Übung in der Kategorie Lehre
SWS	4

Lehrende

• Prof. Dr. Robert Bredereck

Räume und Zeiten

Die Zeiten der Veranstaltung stehen nicht fest.

Studienbereiche

• Vorlesungsverzeichnis Wintersemester 2026/27 > Studienkommission 4: Mathematik und Informatik > Institut für Informatik

Kommentar/Beschreibung

The first chapter covers some topics from the Chomsky
hierarchy: the Myhill-Nerode theorem (how to construct a
minimal finite automaton), deterministic PDA’s, type 1
languages, normalform for type 0 and type 1 languages,
Ehrenfeucht's theorem and Lindenmayer systems, a class of
grammars that is orthogonal to parts of the Chomsky hierarchy.
Chapter 2 discusses undecidability results in greater depth
(Post's Correspondence theorem, (primitive) recursive
functions, Hilbert's 10. problem (solving diophantine
equations)). We also cover Rice's theorem and its analogue for
grammars. Makanin's problem (word equations over a free
monoid) is decidable but not primitive recursive.

Chapters 3 and 4 cover classical complexity results: time versus
space, speed-up, gap-theorem, union-theorem and complexity
classes: PH (the polynomial hierarchy), PSPACE, EXPSPACE
and most of their interesting subclasses. We also cover closure
properties and the Immerman/Szelepcsényi theorem.
Chapter 5 covers the arithmetical and analytical hierarchy
(extending EXPSPACE into the undecidable) and discusses
descriptive complexity: can we find logics corresponding to
complexity classes (Fagin's theorem).