Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2012/13 / Komplexitätstheorie


Inhaltsbereich

Komplexitätstheorie

Vorlesung, 3-std., Mo 10-12, Do 14-16, Hofmann; Übungen 2-std., Mi 12-14

Aktuelles

  • Die Ergebnisse können Sie unter Angabe Ihrer Matrikelnummer in unserem Sekretariat erfragen (sigrid.roden[at]ifi.lmu.de)
  • Die Nachholklausur wurde auf 12:00 verschoben.
  • Am 10.04.2013 findet um 12:00 Uhr im Hörsaal BU 101 eine Nachholklausur statt. Bitte bis zum 03.04.2013 für die Nachholklausur anmelden.
  • Man kann sich ab jetzt bei Uniworx für die Klausur anmelden.
  • Die Klausur findet am 07.02. zur Vorlesungszeit (14:00-16:00) statt. 
  • ACHTUNG: Die Klausur findet im HGB Hörsaal B 015 statt!

  • http://imgs.xkcd.com/comics/np_complete.png
  • Hausaufgaben dürfen nunmehr bis Mittwoch 14:00 abgegeben werden (in Übung, Vorlesung, oder Sekretariat).
  • Form und Termin der Prüfung richtet sich nach der Teilnehmerzahl (Klausur oder muendlich) und wird in der ersten Semesterwoche festgelegt.  
  • Die Veranstaltung kann in diesem Semester ausnahmsweise anstelle von "Formale Spezifikation und Verifikation" belegt werden.
  • Prüfung: In der letzten Semesterwoche findet eine Klausur oder mündliche Prüfung statt; Hausaufgaben sind *keine* Teilnahmevoraussetzung. Bei den Hausaufgaben erzielte Punkte können wie am Institut üblich die Note verbessern.

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 Crescenzi. Für das Kapitel Schaltkreiskomplexität wird eine korrigierte Mitschrift zur Verfügung gestellt.


Organisation

  • Umfang: 3+2 Semesterwochenstunden
  • Voraussetzung: Grundstudiumsvorlesungen der Informatik
  • Vorlesung und Übung: Prof. Martin Hofmann

Die Vorlesung wird anerkannt:

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

Zeit und Ort

Veranstaltung Zeit Ort Beginn
Vorlesung Mo, 10 - 12 Uhr Raum 016 (Amalienstraße 73A) 15.10.2012
Vorlesung Do, 14 - 16 Uhr Raum 118 (Amalienstraße 73A) 18.10.2012
Übung Mi, 12 - 14 Uhr Raum C 003 (Oettingenstraße 67) 24.10.2012

 


Planung

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

Zurzeit ist für die Vorlesung folgende Planung vorgesehen:

Nr. Datum Thema
1. 15.10. Einführung, Übersicht, Wdh FSK

2. 18.10.

Zeitkomplexität. Die Komplexität nichtdeterministischer TM ist im Buch (und waehrend der Vorlesung) falsch. Richtig ist: TIME_T(x)=Laenge der laengsten Berechnung von T auf x. Zeithierarchiesatz: Falls t:N->N zeitkonstruierbar und t(n)>=n, so ist DTIME(t) echt enthalten in DTIME((n * t(n))^2).
Definition der Komplexitaetsklassen P,NP, E, NE, EXP, NEXP.
Satz: P=NP ==> E=NE. Beweis naechstes Mal.


3. 22.10. Wdh P,NP,E,NE, zeitkonstruierbar. Gap Theorem ohne Beweis. Folgerung P=/=E aus Zeithierarchiesatz. P=NP=>E=NE durch Padding bewiesen. Beispiele von Problemen in P und zugehoerige Algorithmen: ggT nach Euklid, dynamische Programmierung am Beispiel von All-Pairs-Shortest-Path.


4.
25.10. Laufzeitabschaetzung fuer ggT nach Eukid ohne Fibonaccizahlen nach Bovet-Crescenzi. Wdh Aussagenlogik, KNF. Skizzierung 2SAT in P. Definition NP-Vollständigkeit. Satz von Cook: SAT ist NP vollstaendig. Beweis nur skizziert.


29.10.


01.11.

5. 05.11. Orakel-Turingmaschinen, die Klassen P^A und NP^A fuer Orakel A. Satz: es gibt Sprache A, sodass P^A=NP^A. Effektive Aufzaehlung det. polynomieller Orakel Turingmaschinen.

6. 08.11. Konstruktion eines Orakels B sodass P^B =/= NP^B (Baker-Solovay). Def.: Duenne (sparse) Sprachen. Beweis, dass UNSAT (co-NP vollstaendig) in NP ist unter der Annahme, dass eine duenne NP-vollstaendige Sprache S existiert mit der zusaetzlichen Eigenschaft, dass die Zensusfunktion von S in FP ist.

7. 12.11. Wdh: Relativierung, Orakelmaschinen. Beweis, dass falls eine Menge S wie oben existiert, so ist P=NP. Die Annahme "Zensusfunktion in FP" wurde dann noch eliminiert -> Satz von Mahaney: Existenz einer duennen, NP-vollstaendigen Menge impliziert P=NP.
Definition der ersten beiden Stufen der polynomiellen Hierarchie

8.
15.11. Polynomielle Hierarchie (PH), Charakterisierung durch quantifizierte Boolesche Formeln mit bestimmter Alternierungstiefe, Satz von Karp-Lipton: SAT hat polynomielle Schaltkreise -> PH kollabiert (nur Aussage illustriert, Beweis am 19.11.)

9. 19.11. Beweis des Satzes von Karp-Lipton. Platzkomplexitaet: Grundlegende Definitionen,  Satz von Savitch (NSPACE(s(n)) <= DSPACE(s(n)^2)).

10. 22.11. Satz von Immerman-Szelepcsenyi. Logarithmischer Platz (det. und nichtdet.), Beispiele von LOGSPACE Algorithmen, NLOGSPACE <= P.

11.
26.11. LOGSPACE Reduktionen, P-Vollstaendigkeit. HORNSAT: (Un)erfuellbarkeit von Hornklauseln. Beweis der P-Vollstaendigkeit dieses Problems.


29.11.


03.12.



06.12.


12.
10.12. Polynomieller Platz und QBF (quantifizierte Boole'sche Formeln). PSPACE-Vollstaendigkeit von QBF.  Nachtrag: Satz von Reingold. Nur Aussage, kein Beweis.

13. 13.12. Randomisierte Algorithmen: Miller-Rabin Primzahltest, Gleichheit von Polynomen, Existenz von perfektem Matching.

14. 17.12. Probabilistische Klassen: PP, BPP, R, co-R


20.12.

15.
07.01. Interaktive Beweissysteme (IP), coNP <= IP

16. 10.01. IP=PSPACE. Def. von PCP. 

17. 14.01. PCP Theorem (ohne Beweis). Folgerung: MAXCLIQUE kann nicht effizient approximiert werden, es sei denn P=NP.

18. 17.01. Beweis von NP <= PCP(poly(n),1) nach Motwani


21.01.


24.01.

19.
28.01. Schaltkreiskomplexitaet (ASCII Notiz zu dieser und der naechsten Vorlesung)

20.
31.01. Satz von Razborov und Smolensky: PARITY nicht in AC0[mod3]


04.02.



07.02.
Klausur

 


Klausur

Die Klausur wird am 07.02. zur Vorlesungszeit stattfinden. Die Bearbeitungszeit betraegt 60 Min.

Bitte bei Uniworx für die Klausur anmelden.

Gegen Ende der vorlesungsfreien Zeit werden wir bei Bedarf eine Nachklausur anbieten.


Übungen

Die Hausaufgaben müssen jeweils bis 12:00 mittags am genannten Termin in der Vorlesung oder im Sekretariat bei Fr Roden (Oet L1.03) in Papierform abgegeben 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.

Zur Motivation:

 

Artikelaktionen


Funktionsleiste