Links und Funktionen
Sprachumschaltung
Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2015/16 / Komplexitätstheorie
Inhaltsbereich

Komplexitätstheorie

Vorlesung, 3-std., Mo 10-12, Do 10-12, Hofmann, Schöpp; Übungen 2-std., Di 14-16, Schöpp
Aktuelles | Inhalt | Organisation | Zeit und Ort | Klausur | Weiterführende Informationen

Aktuelles

 

  • Die mündlichen Nachprüfungen finden am Dienstag, den 5. April im Raum L107, Oettingenstr. 67 zu folgenden Zeiten statt.
    MatrikelnummerZeit
    entfernt 13:00-13:30
    entfernt 13:30-14:00
    entfernt 14:00-14:30
    entfernt 14:30-15:00
  • Die Anmeldung zur Klausur ist nun über Uniworx möglich.
  • Die Veranstaltung am 04.02. (Wdh und Ausblick) findet entgegen der mündlichen Ankündigung in der Vorlesung heute (1.2.) statt. Ich werde auf Fragen und Wiederholungswuensche vom Publikum eingehen und evtl noch etwas mehr zu PCP vortragen. Wahrscheinlich werden wir etwas frueher aufhoeren. -- MH

Inhalt

Die Komplexitätstheorie beschäftigt sich mit der Klassifikation von Algorithmen und Berechnungsproblemen nach ihrem Ressourcenverbrauch, z.B. Rechenzeit oder benötigtem Speicherplatz. Probleme mit gleichartigem Ressourcenverbrauch werden zu Komplexitätsklassen zusammengefasst. Die bekanntesten Komplexitätsklassen sind sicherlich P und NP, die die in polynomieller Zeit deterministisch bzw. nicht-deterministisch lösbaren Probleme umfassen.

P und NP sind jedoch nur zwei Beispiele von Komplexitätsklassen. Andere Klassen ergeben sich etwa bei der Untersuchung der effizienten Parallelisierbarkeit von Problemen, der Lösbarkeit durch zufallsgesteuerte oder interaktive Algorithmen, der approximativen Lösung von Problemen, um nur einige Beispiele zu nennen.

Übersicht

  1. Motivation und Einführung
  2. Turingmaschinen, Berechenbarkeit, Komplexitätsklassen
  3. Die Klassen P und NP
  4. Platzkomplexität
  5. Alternierung und Hierarchien
  6. Komplexität von Schaltkreisen
  7. Interaktive und probabilistische Algorithmen

Die Vorlesung richtet sich im wesentlichen nach dem Buch von Bovet und Crescenzi.

Organisation

  • Umfang: 3+2 Semesterwochenstunden
  • Voraussetzung: Grundstudiumsvorlesungen der Informatik
  • Vorlesung und Übung: Prof. Martin Hofmann, Dr. Ulrich Schöpp

Die Vorlesung wird anerkannt für:

  • Studierende im Studiengang Informatik Master für das Modul Algorithmik und Komplexität
  • Studierende im Studiengang Medieninformatik Master für das Modul Vertiefende Themen der Informatik für Master
  • Studierende in den Studiengängen Informatik und Medieninformatik Bachelor für das Modul Vertiefende Themen der (Medien-) Informatik
  • Studierende mit Nebenfach Informatik nach Vereinbarung
  • Studierende im Studiengang Informatik Diplom im Prüfungsfach Programmierung und Grundlagen, Teilbereich Theoretische Informatik

Zeit und Ort

VeranstaltungZeitOrtBeginn
Vorlesung Mo, 10-12 Uhr Amalienstr. 73A - 114 12.10.2015
Vorlesung Do, 10-12 Uhr Amalienstr. 73A - 114 15.10.2015
Übung Di, 14-16 Uhr Geschw.-Scholl-Pl. 1 (A) - A U115 20.10.2015

 

Planung

Da die Vorlesung trotz der zwei wöchentlichen Vorlesungstermine insgesamt nur den Umfang von 3 SWS hat, entfallen einige Vorlesungstermine. Die Übungen finden durchgehend statt.

Vorläufige Vorlesungsplanung:

Nr.DatumThemaHinweise
1. 12.10. Inhalt, Organisation, Turingmaschinen
2. 15.10. Zeitkomplexität, Speedup Theorem
3. 19.10. Die Klassen P,NP,E,NE,EXP,NEXP. Paddingtechnik
22.10.
26.10.
29.10.
02.11.
05.11.
4. 09.11. Definition FP (in polynomieller Zeit berechenbare Funktionen).
Definition NP-vollständig, Satz von Cook-Levin (SAT ist  NP-vollständig
5. 12.11. Satz von Ladner (Wenn P =/= NP, dann gibt es Probleme in NP \ P, die doch nicht NP-vollständig sind.)
6. 16.11. Definition Orakel-Turingmaschinen, Definition der relativierten Klassen P^C und NP^C für Sprachen C. Veranschaulichung  von P^SAT und NP^SAT. Satz: es gibt Sprache C sodass P^C=NP^C.
7. 19.11. Konstruktion eines Orakels C sodass P^C =/= NP^C. Definition der Polynomiellen Hierarchie (PH). Charakterisierung der PH durch quantifizierte Prädikate in P.
8. 23.11. Selbstreduzierbarkeit von SAT; Satz von Karp-Lipton: Falls polynomiell grosse Schaltkreise für SAT existieren, so folgt Sigma^P_2=Pi^P_2 also ein Kollaps der polynomiellen Hierarchie. Definition Platzkomplexität.
9. 26.11. Definition platzkonstruierbare Funktion. Definition DSPACE(s(n)), NSPACE(s(n)), LOGSPACE=DSPACE(log(n)), NLOGSPACE=NSPACE(log(n)), PSPACE=DSPACE(poly(n)).
 Folgerung aus Platzhierarchiesatz (wurde weder formalisiert, noch bewiesen):
 LOGSPACE ist echt enthalten in PSPACE. Typische Probleme in LOGSPACE, NLOGSPACE, PSPACE. Beziehungen zwischen Platz und Zeit (ohne Beweis). Satz von Savitch: NSPACE(s(n)) enthalten in DSPACE(s(n)2)
10. 30.11. Satz von Immerman-Szelepcsenyi. Platzbeschränkte Turingmaschinen mit Stack als besonderes Arbeitsband. Definition der Klasse NSPACE(s(n))+STACK.
11. 03.12. Satz von Cook: NSPACE(s(n))+STACK = DTIME(2^{O(s(n))}). LOGSPACE Reduzierbarkeit. NLOGSPACE-Vollständgkeit, P-Vollständigkeit. REACH ist NLOGSPACE-vollständig
12. 07.12. P-Vollständigkeit von HORN-SAT. PSPACE-Vollständigkeit von QBF.
13. 10.12. PSPACE Vollstaendigkeit von QBF SAT, 2 Personen Spiele, Chomp
14. 14.12. PSPACE Vollstaendigkeit von Generalized Geography und Universalitaet von NEA. ASCII Notiz hier
15. 17.12. Def.: Zeigerstrukturen und Jumping Automata on Graphs. Satz von Cook-Rackoff (nur Aussage). ASCII-Notiz hier.
16. 21.12.

Satz von Cook-Rackoff: Beweisidee. Ueberblick ueber Arbeiten der LFE TCS  zu JAGs. ASCII-Notiz hier.  ASCII-Notiz von 2008/09 zu Programmiersprachen und Komplexitaet (nicht in der VL behandelt)
17. 07.01. Miller-Rabin Primzahltest. Probabilistischer Test, ob ein multivariates Polynom identisch Null ist durch Einsetzen von Zufallswerten. Definition "perfektes Matching".  ASCII-Notiz.
18. 11.01. Probabilistischer Test auf perfektes Matching mit Satz von Tutte. Monte-Carlo und Las Vegas
Algorithmen. Probabilistische Turingmaschinen. Definition der Klassen PP, R, co-R, BPP, ZPP.
19. 14.01. Interaktive Beweissysteme, die Komplexitätsklassen DIP und IP.  DIP=NP und IP enthalten in PSPACE. In IP ist es möglich  zu entscheiden, ob zwei Graphen nicht isomorph sind.
. 18.01.
21.01.
20. 25.01. IP Protokoll fuer co-3SAT mithilfe von Arithmetisierung
21. 28.01. PSPACE=IP (Beweisskizze). Aussage des PCP-Theorems (ohne Beweis!). Schaltkreiskomplexität: grundlegende Definitionen.
22. 01.02. Satz von Furst-Saxe-Sipser: PARITY nicht in AC(0). ASCII Notiz
23. 04.02. Wdh. Ausblick

Klausur

Erstklausur

  • Termin: 3. März 2016, 14-16 Uhr (Einlass: 14 Uhr; Beginn: 14:15 Uhr)
  • Ort: Hörsaal M 110 (HGB)
  • Bearbeitungszeit: 90 Minuten
  • Die Klausur findet ohne Hilfsmittel statt. Insbesondere sind keine schriftlichen Unterlagen, keine Taschenrechner oder andere Rechner, keine Mobiltelefone oder andere Kommunikationsmittel erlaubt.
  • Mitzubringen sind:
    • gültiger Immatrikulationsnachweis für dieses Semester
    • gültiger Personalausweis oder Pass mit Lichtbild
    • Schreibzeug (keine Rot- und Grünstifte, kein Bleistift)
    • Eigenes Papier ist nicht erforderlich und darf für die Prüfung nicht benutzt werden.

Nachklausur

Übungen

Übungsblätter finden Sie bei UniWorX.

Ausgewählte Aufgaben sind mit einer Punktzahl gekennzeichnet. Durch Lösung solcher Aufgaben kann ein Bonus auf die Klausurnote erworben werden. Ab 50% der Punkte beträgt der Notenbonus 0,3, ab 75% dann 0,7. Aufgaben, die mit Punkten gekennzeichnet sind und deshalb zum Notenbonus zählen, müssen allein bearbeitet werden.

Weiterführende Informationen

Literatur

  • Bovet, Crescenzi. Introduction to the Theory of Complexity. Prentice Hall. New York.1994.
  • C. Papadimitriou. Computational Complexity. Addison-Wesley. Reading. 1995.
  • I. Wegener. Komplexitätstheorie: Grenzen der Effizienz von Algorithmen. Springer. 2003.
  • Ein hervorragendes Vorlesungsskript von Oded Goldreich, das weit mehr, aber auch nicht alles abdeckt, als wir in der Vorlesung behandeln werden.
  • S. Arora und B. Barak. Complexity Theory: A Modern Approach (fast fertige Vorabversion hier). In diesem Buch sind fast alle Themen der Vorlesung abgedeckt.
  • S.A. Cook and C.W. Rackoff. Space lower bounds for maze threadability on restricted machines. SIAM Journal on Computing, 9:636–652, 1980. Formalisierte und verallgemeinerte Version von U Schöpp: www2.tcs.ifi.lmu.de/~schoepp/Docs/formalcr.pdf
  • Arbeiten zu PURPLE: siehe z.B. hier und hier

Zur Motivation:

 

Artikelaktionen

Funktionsleiste