Vorlesung + Übung: Komplexitätstheorie - Details

Allgemeine Informationen

Veranstaltungsname	Vorlesung + Übung: Komplexitätstheorie
Veranstaltungsnummer	S 1228
Semester	SS 2025
Aktuelle Anzahl der Teilnehmenden	1
Heimat-Einrichtung	Institut für Informatik
Veranstaltungstyp	Vorlesung + Übung in der Kategorie Lehre
Bemerkung	Master, Hauptstudium Informatik/Wirtschaftsinformatik
SWS	4

Lehrende

• Prof. Dr. Robert Bredereck

Räume und Zeiten

Keine Raumangabe

Studienbereiche

• Vorlesungsverzeichnis Sommersemester 2025 > 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).