Vorlesung + Übung: Komplexitätstheorie - Details

Vorlesung + Übung: Komplexitätstheorie - Details

Nachrichtenbox schließen
Sie sind nicht in Stud.IP angemeldet.

Allgemeine Informationen

Veranstaltungsname Vorlesung + Übung: Komplexitätstheorie
Veranstaltungsnummer W 1228
Semester WS 2016/17
Aktuelle Anzahl der Teilnehmenden 30
Heimat-Einrichtung Institut für Informatik
Veranstaltungstyp Vorlesung + Übung in der Kategorie Lehre
Erster Termin Mittwoch, 26.10.2016 10:00 - 12:00, Ort: (D8-210 IfI - Seminarraum 210)
Bemerkung Master, Hauptstudium Informatik/Wirtschaftsinformatik
SWS 4

Räume und Zeiten

(D8-210 IfI - Seminarraum 210)
Mittwoch: 10:00 - 12:00, wöchentlich (14x)
Donnerstag: 10:00 - 12:00, wöchentlich (14x)

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).

Zugelassenene Nutzerdomänen:

  • ecampus Göttingen
  • Leibniz Universität Hannover
  • TU Braunschweig
  • Universität Göttingen
  • Universitätsmedizin Göttingen