In der Vorlesung GTI wurde bereits die NP-Vollständigkeitstheorie als wichtiger Teilbereich der Komplexitätstheorie vorgestellt. Unter der Annahme, dass P ungleich NP ist, können wir mit diesem Werkzeug für viele in der Praxis auftretenden Probleme (bzw. deren Abstraktionen) nachweisen, dass sie nicht exakt in Polynomialzeit lösbar sind. Um für Optimierungsprobleme auch die Existenz von pseudopolynomiellen Algorithmen oder guten Approximationsalgorithmen ausschließen zu können, werden Erweiterungen der bekannten Reduktionskonzepte benötigt, die hier in der Vorlesung vorgestellt werden.
Einen neuen Ansatz zur Untersuchung der Komplexität von Problemen stellen interaktive Beweissysteme dar, bei denen ein als "Beweiser" agierender Spieler eine als "Verifiziererin" agierende Partnerin mit Hilfe eines randomisierten Kommunikationsprotokolls davon überzeugen soll, Eingaben für ein bestimmtes Problem mit hoher Wahrscheinlichkeit richtig in Lösungen bzw. Nichtlösungen zu klassifizieren. Die in der Vorlesung vorgestellten interaktiven Beweissysteme für das Graphisomorphieproblem liefern ein starkes Argument dafür, warum dieses bisher nicht effizient lösbare Problem vermutlich nicht NP-vollständig ist.
Interaktive Beweissysteme stecken auch hinter einer der revolutionärsten Erfindungen der theoretischen Informatik der letzten Jahre, der PCP-Theorie (PCP = probabilistically checkable proof). Diese liefert die Möglichkeit, bezüglich der Güteschranken viel genauere Nichtapproximierbarkeitsergebnisse zu zeigen, als dies mit den klassischen Reduktionsmethoden möglich war. In der Vorlesung werden wir das PCP-Theorem als zentrales Ergebnis dieser Theorie kennen lernen und dessen Anwendungen diskutieren.
Für viele Berechnungsmodelle, z.B. Schaltkreise und eingeschränkte Turingmaschinen, kann man die Schwierigkeit von Problemen nachweisen, indem man die zur Verfügung stehende "Hardware" in Teile zerlegt und argumentiert, dass zur Lösung des Problems viel Kommunikation zwischen diesen Teilen erforderlich ist. Dies liefert die Motivation für die Untersuchung von Kommunikationsspielen, bei denen die Teilnehmer jeweils nur einen Teil der Eingabe besitzen und gemeinsam eine Funktion auf der Gesamteingabe berechnen sollen, indem sie möglichst wenig miteinander kommunizieren. Wir behandeln einige wichtige Beispielprobleme für dieses Modell und wenden die erhaltenen Ergebnisse zum Nachweis von unteren Schranken an.
Randomisierte Algorithmen benutzen in der Theorie unabhängige, gleichverteilte Zufallsbits, in der Praxis aber meist einfache Pseudozufallszahlengeneratoren (z.B. lineare Kongruenzgeneratoren). Die theoretischen Aussagen über die Fehlerwahrscheinlichkeit der damit betriebenen randomisierten Algorithmen sind dann aber nicht länger gültig, sodass wir einen rein heuristischen Ansatz erhalten. In der Vorlesung werden stärkere Konstruktionen solcher Pseudozufallszahlengeneratoren vorgestellt, die mit nur sehr wenigen "echten" Zufallsbits gefüttert werden müssen und bei deren Einsatz in randomisierten Algorithmen sich die Fehlergarantie nur unwesentlich verschlechtert.
M. Sauerhoff