Hierarchien (Vorlesung)

Hierarchien in der Komplexitätstheorie bilden einen uniformen Ansatz, komplexitätstheoretisch verschieden schwere Probleme zu klassifizieren und miteinander zu vergleichen. Hierarchien erlauben dabei eine sehr genaue Untersuchung der Eigenschaften der Probleme innerhalb der einzelnen Stufen. Werden Hierarchien durch Maschinenmodelle definiert, erlauben sie auch eine gute Untersuchung der Berechnungskraft dieser Modelle.

Vorlesungsinhalt

Wir werden uns mit verschiedenen Hierarchien beschäftigen und deren Eigenschaften untersuchen. Eine zentrale Frage im Zusammenhang mit Hierarchien wird stets sein, ob die Hierarchie tatsächlich echt ist, das heißt, ob die einzelnen Stufen der Hierarchie neue Klassen beschreiben. Wir werden sehen, daß sich ein Kollaps innerhalb einer Hierarchie auch auf andere Hierarchien auswirken kann. Weiterhin werden wir nach vollständigen Problemen für die Stufen einer Hierarchie suchen.

Die folgenden Hierarchien werden betrachtet:

  • Hausdorff- oder Boolesche Hierarchie über NP
  • Fragehierarchie über NP
  • probabilistische Hierarchien über PL und PP
  • Arthur-Merlin-Hierarchie.

Teilnehmer

Die Vorlesung richtet sich einerseits an Studenten, die ihr Wissen im Bereich Komplexitätstheorie vertiefen möchten, andererseits an Studenten, die sich im Umgang mit abstrakten Problemen bilden möchten.

Teilnahmevoraussetzungen

Die Vorlesung kann als Ergänzung zur Vorlesung "Komplexitätstheorie" betrachtet werden, aber auch als eigenständige Veranstaltung. Da alle notwendigen Begriffe innerhalb der Vorlesung definiert werden, sind spezielle Vorkenntnisse, die über das Wissen aus der Grundlagenveranstaltung hinausgehen, nicht erforderlich.

Termine

Vorlesungdienstags, 8 Uhr c.t.HZ 201erstmals: 24. April

Dozent

Daniel Meister