Komplexitätstheorie B (Vorlesung)

Einführung

Die beiden Polynomialzeitkomplexitätsklassen P und NP spielen in der Informatik, und darüber hinaus, eine herausragende Rolle. Während sich die Klasse P weitgehend geheimnislos zeigt, steckt NP voller Überraschungen. Im Rahmen der Vorlesung sollen einige dieser "Überraschungen" präsentiert werden. Neben dem Kennenlernen verschieden(artig)er Resultate und (zum Teil algorithmischer) Beweistechniken soll die Vorlesung auch ein tiefergehendes Verständnis für das Wesen des Nichtdeterminismus ermöglichen, insbesondere im Verhältnis zum Determinismus.

Vorlesungsinhalt

Die Vorlesung ist in zwei Teile gegliedert. In einem ersten Teil werden wir die Klasse NP bezüglich verschiedener Reduzierbarkeitsbegriffe auf die folgenden Fragen hin untersuchen:

  • Existenz (spezieller) vollständiger Probleme
  • Abgeschlossenheit.

Wir werden im speziellen sehen, daß viele "positive" Antworten sehr unwahrscheinlich sind, da sie einen Kollaps der Polynomialzeithierarchie zur Folge haben.

In einem zweiten Teil werden wir uns mit vollständigen Problemen bezüglich der Many-one-Reduzierbarkeit beschäftigen. Wir werden hier insbesondere eine kleine Auswahl an verschiedenartigen Problemen kennenlernen. Ein Höhepunkt wird das PCP-Theorem sein, welches NP auf ungewöhnliche Weise beschreibt.

Teilnahmevoraussetzungen

Die Vorlesung knüpft thematisch an Komplexitätstheorie A an, kann davon aber auch unabhängig besucht werden. Die wichtigen und vorausgesetzten Begriffe sind aus den Grundvorlesungen zur Theoretischen Informatik bekannt. Alles weitere wird in Vorlesung und Übung definiert und behandelt.