Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Hauptinhalt

Komplexitätstheorie (und effiziente Algorithmen)

Wintersemester 2008/2009

Veranstalter:Carsten Witt
Termine: Montag 12:15-13:45 Uhr OH 14, E 23
Mittwoch 12:15-13:45 Uhr OH 14, E 23
Beginn: 13. Oktober 2008

[Inhalt] [Begleitmaterial] [Vorlesungsfolien] [Übungen]

Inhalt

Die Veranstaltung richtet sich an Student(inn)en der Diplomstudiengänge in Informatik und Angewandter Informatik und zugleich an Student(inn)en der Masterstudiengänge, dort mit dem Namen "Komplexitätstheorie" (vgl. Modulhandbuch). In den Diplomstudiengängen hat diese Vorlesung im Wintersemester den Schwerpunkt Komplexitätstheorie und im Sommersemester den Schwerpunkt effiziente Algorithmen. Ein Besuch beider Vorlesungen ist sinnvoll und für eine Spezialisierung in diesen Bereichen sehr nützlich.

Wenn wir in der glücklichen Lage sind, einen effizienten Algorithmus für ein von uns zu lösendes Problem gefunden zu haben, ist eine naheliegende Frage, ob z. B. dessen Laufzeit noch wesentlich verbessert werden kann. Kann man zeigen, dass kein Algorithmus für dieses Problem asymptotisch eine bessere Laufzeit hat? Für viele praktisch wichtige Probleme sind andererseits bisher überhaupt keine effizienten Algorithmen bekannt - wie können wir nachweisen, dass solche Probleme inhärent schwierig sind? Die Vorlesung Komplexitätstheorie beschäftigt sich mit den aktuell vorhandenen Möglichkeiten, solche Fragen zu beantworten.

In den Vorlesungen GTI und TIfAI 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.

In den Anwendungen spielen randomisierte Suchheuristiken wie evolutionäre Algorithmen oder Simulated Annealing eine immer wichtigere Rolle. Diese Algorithmen nutzen nicht die volle Information über die Eingabe. Die Komplexitätstheorie reagiert auf alle neuen algorithmischen Entwicklungen und wir stellen eine Theorie vor, die Probleme darauf untersucht, ob sie mit randomisierten Suchheuristiken effizient lösbar sind.

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

Insgesamt ergibt sich ein Einblick in die moderne Komplexitätstheorie mit überraschend vielen konkreten Ergebnissen, die den Entwurf effizienter Algorithmen in die richtigen Bahnen lenken.

Begleitmaterial

Die Vorlesung wird sich im Wesentlichen an folgendem Buch orientieren:
Ingo Wegener, "Komplexitätstheorie -- Grenzen der Effizienz von Algorithmen", Springer, 2003.
Geplant ist die Behandlung der Kapitel 7-15.

Vorlesungsfolien: PDF-Datei (Stand 04.02.2009)

In der Vorlesung behandelte Themen

  • 13.10.2008: Vorstellung, Wiederholung GTI: Turingmaschinen, Ressourcenmessung, Randomisierung und Nichtdeterminismus, randomisierte Komplexitätsklassen, Rate-Verifikations-Turingmaschinen, NP-Vollständigkeitstheorie, Entscheidungs- versus Optimierungsvarianten, Reduktionskonzepte Restriktion, lokale Ersetzung, verbundene Komponenten
  • 15.10.2008: Wiederholung GTI: Turingreduktion, NP-Äquivalenz, Problemvarianten und Reduktionen unter den Varianten; pseudopolynomielle Algorithmen und starke NP-Vollständigkeit, starke NP-Vollständigkeit von TSP, Definition 3-PARTITION; Approximationsprobleme: Definition, Güte, Definition Approximationsalgorithmen, triviale Aproximationsalgorithmen für CLIQUE, Definition APX, PTAS und FPTAS
  • 20.10.2008: Approximationsalgorithmen: APX-Algorithmen für Vertex Cover, Max-SAT mit Derandomisierung und Bin-Packing, PTAS für Makespan Scheduling, FPTAS für Rucksackproblem, Lückentechnik: Definition Lückenproblem, Anwendung auf TSP, Probleme mit kleinen Lösungswerten, Nichtexistenz von FPTAS, Nichtapproximierbarkeit von MIN-GC und MIN-BP, Boosting-Technik für MIN-GC, untere Schranke für asymptotische Worst-Case-Güte
  • 22.10.2008: PTAS-Reduktionen, Implikationen für APX- und PTAS-Probleme, Reflexivität und Transitivität der PTAS-Reduktion, approximationserhaltende Reduktionen an Beispielen, Gegenbeispiel mit MAX-4-SAT, Klasse NPO, Einschränkung auf NPO-Probleme, NPO-Vollständigkeit, MAX-W-SAT, NPO-Vollständigkeit von MAX-W-SAT
  • 27.10.2008: Black-Box-Optimierung, Einführung Black-Box-Algorithmen, Zweipersonen-Nullsummenspiele, Yaos Minimaxprinzip, untere Schranken für randomsierte Suchverfahren, Beispiel Needle-in-a-haystack
  • 29.10.2008: Black-Box-Optimierung: Trap-Funktionen, Black-Box-Komplexität unimodaler Funktionen, Beweis von Satz 9.3.4 bis auf die Argumentation für Mnah
  • 03.11.2008: Beweis der untere Schranke für Black-Box-Komplexität unimodaler Funktionen beendet, No-free-Lunch-Theorem, Komplexitätsklassen innerhalb von NP und co-NP: Klasse NPI, Diskussion von NPI-Problemen, NP vs. co-NP, Folgerungen daraus
  • 05.11.2008: Orakelturingmaschinen, Orakelklassen P(C) und NP(C), MEC aus NP(NP), Definition der polynomiellen Hierachie, Inklusionsbeziehungen und Eigenschaften der Klassen (Lemma 10.4.2), Logikcharakterisierung und Satz von Wrathall angegeben
  • 10.11.2008: Beweis des Satzes von Wrathall (Satz 10.4.3), Implikationen für die polynomielle Hierarchie (Satz 10.4.5 und Folgerung 10.4.6) , SATcirk als Sigma-k-vollständiges Problem, Definition PSPACE
  • 12.11.2008: Satz von Sipser-Gacs-Lautemann (BPP Teilmenge Sigma2), weitere Folgerungen, Satz 10.5.6 (NP Teilmenge BPP impliziert NP=RP), Satz 10.5.5 (Folgerung PH Teilmenge BPP) mit Selbstreduzierbarkeit und Vertauschungslemma
  • 17.11.2008: Relativierte Komplexitätstheorie, Exkurs Hierarchiesätze, Exkurs zum universellen Hashing etc., interaktive Beweissysteme, Klasse IP und IP(k), Einordnung von GI-quer in IP(2) begonnen
  • 19.11.2008: letzten Beweis zu Ende gebracht, Quantorenklassen, AM-Protokolle, Beweis GI-quer in AM begonnen
  • 24.11.2008: Beweis GI-quer in AM beendet, Konsequenzen aus NP-Vollständigkeit, Zero-Knowledge-Protokolle: Motivation, Beispiel "magische Tür", Protokoll für GI, Definition statistische und allgemeine Zero-Knowledge-Eigenschaft
  • 26.11.2008: Protokoll mit allgemeiner Zero-Knowledge-Eigenschaft für HC (Korrektur siehe Folien), Einführung PCP, Def. randomisierter Beweisverifizierer, PCP-Theorem vorgestellt, Beweis für abgeschwächtes Resultat angekündigt
  • 01.12.2008: NP = PCP(n3,1), Beweisidee vorgestellt, Details für Beweisverifizierer und Linearitätstest
  • 03.12.2008: Beweis von NP = PCP(n3,1) beendet, Nichtapproximierbarkeitsresultat für MAX-3-SAT bewiesen
  • 08.12.2008: Nichtapproximierbarkeit von MAX-CLIQUE, MAX-APX-Vollständigkeit von MAX-3-SAT: Beweis begonnen
  • 10.12.2008: MAX-APX-Vollständigkeit von MAX-3-SAT und Reduktion von MIN-APX auf MAX-APX abschließend bewiesen
  • 15.12.2008: Platzkomplexität: Definitionen, Bezug zur Chomsky-Hierarchie, Platz versus Zeit (beachte Korrektur auf Folie 480), QBF aus PSPACE, WCSL aus PSPACE bewiesen
  • 17.12.2008: Abschluss PSPACE-Vollständigkeit, Satz von Savitch, Satz von Immerman/Szelepcsényi, LOGSPACE-Reduktionen und Vollständigkeit von DSTCON, Klasse #P und vollständige Probleme
  • 05.01.2009: Nichuniforme Berechnungsmodelle: Schaltkreise, Simulation durch (nichtuniforme) TM und zurück, quadratischer Tiefenzuwachs, Branchingprogramme als alternative nichtuniformes Modell, Verknüpfung zwischen TM-Platz und Logarithmus der Branchingprogrammgröße, polynomielle Schaltkreise für Probleme in BPP
  • 07.01.2009: Kommunikationskomplexität: Einführung, Def. Protokollbaum, Beispiel Medianberechnung, Kommunikationsmatrix, kombinatorische Rechtecke, Untere-Schranken-Methoden Rechteckmaßmethode, Anwendung auf EQ und GT, Def. Unterscheidungsmengen und vorige untere Schranken auf diesem Weg
  • 14.01.2009: Definition DISJ und IP, Anwendung der Rechteckmaßmtehode und Unterscheidungsmengenmethode, Rangmethode, verbesserte Schranke für IP mit Rückgriff auf die Hadamardmatrix, Rechteckreduktionen, beliebige Partionen der Eingabemenge und balancierte Partionen, Maskenvarianten, untere Schranke für MULn-1(a,b) begonnen
  • 19.01.2009: Untere Schranke für MULn-1(a,b) beendet, nichtdeterministische und randomisierte Protokolle, Bezug zu Überdeckungsmaßen NOR etc., Übertragung von Beweismethoden, Schranken für die nichtdet. KK von EQ, GT, DIS, IP und MUL
  • 21.01.2009: fehlerfreie nichtdeterministische KK, C(f)=O(CAND(f) * COR(f)), Komplexitätslandschaft für nichtdet. Protokolle, randomisierte KK, verschiedene Fehlermodelle, Probability Amplification, Derandomisierung
  • 26.01.2009: Randomisierte Protokolle mit öffentlichem Zufall, Anwendung auf EQ, Simulation durch privaten Zufall (Satz von Newman), approximierende Protokolle, Zusammenhang zu rand. Protokollen mit zweiseitigem Fehler über Yaos Minimax-Prinzip
  • 28.01.2009: Diskrepanzmethode, Anwendung auf IP, Anwendungen VLSI-Schaltkreise sowie 1-Band- vs- 2-Band-Turingmaschinen
  • 02.02.2009: Komplexität boolescher Funktionen: Einführung, Größe allgemeiner Schaltkreise, Schranke 2n-3 für Thresholdfunktionen, Tiefe von Schaltkreisen, Bezug zur Formelgröße, Methode von Nechiporuk, Definition ISA
  • 04.02.2009: Nechiporuk-Schranke für ISA, Kommunikationskomplexität von Relationen und Tiefe von Schaltkreisen

Übungen

Übungsgruppen:

Zeit: Ort: Veranstalter:
Gruppe 1: Mittwoch, 16.15-17.45 Uhr OH 14, 304Robin Nunkesser/Martin Sauerhoff
Gruppe 2: Freitag, 12.15-13.45 Uhr OH 14, 104Robin Nunkesser/Martin Sauerhoff

Übungsblätter:

  1. Blatt 1
  2. Blatt 2
  3. Blatt 3
  4. Blatt 4
  5. Blatt 5
  6. Blatt 6
  7. Blatt 7
  8. Blatt 8
  9. Blatt 9
  10. Blatt 10
  11. Blatt 11
  12. Blatt 12
  13. Blatt 13
  14. Blatt 14

Letzte Änderung am 04.02.2009 von C. Witt