http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Komplexitätstheorie

Ablauf

Die Vorlesung findet im Rahmen eines Lesekurses statt. Grundlage dieses Kurses ist das Buch "Computational Complexity: A modern approach" von S. Arora und B. Barak (Cambridge, 2009).

Termine:

  • 28.10.
    • Themen: Kapitel 1 und Abschnitt 2.1 ( ohne 1.5 und 1.7).
    • Übungsaufgaben: 1.3., 1.5. (bitte nur die allgemeine Idee erläutern), 1.14., 1.15.(b)
  • 14.11.
    • Themen: Abschnitt 2.1. -- 2.5.
    • Übungsaufgaben: 2.9., 2.10., 2.13., 2.17. (Anforderung: Exactly One 3SAT als NP-vollständig beweisen. Zusatz: Entwerfen Sie eine Reduktion von EO 3SAT auf Subset Sum.)
  • 18.11.
    • Themen: Kapitel 2 abschließen.
  • 25.11.
    • Themen: NP-Vollständigkeit SubsetSum (pdf, pdf), 3PM (pdf), Kapitel 4: Bis Theorem 4.13 (+ Beweis), jedoch ohne Abschnitt 4.1.3.
  • 28.11.
  • 09.12.
    • Themen: Kapitel 4 abschließen. Kapitel 5 ohne Abschnitte 5.3 und 5.4. Abschnitt 5.5 nur durchlesen.
  • 19.12.
    • Themen: Kapitel 6.1., Kapitel 7. 1 --  7.5
  • 13.1.
    • Themen: Kapitel 7 abschließen, Kapitel 8.1, Kapitel 11.1. bis Seite 241
  • 27.1. und 30.1.
    • Themen: Kapitel 11.2. -- 11.5. Voraussichtlicher Plan: 27.1. Kapitel 11.2. -- 11.4.; 30.1. Kapitel 11.5.
  • 31.1., 11 Uhr
    • Übungstermin! Zu bearbeitende Aufgaben: 7.6., 7.9., 8.1. (Vorsicht: (c) hat es mehr als in sich -- Beweis kann hier nachgelesen werden), 11.1., 11.2., 11.6. (Zusatz zu 11.6.: Zeigen Sie, dass PCP(poly(n),0) = coRP ist.)

Die Diskussionsrunde findet jeweils um 9:00 - 10:30 im Raum 1050, Zusebau, statt.

Weitere Interessenten können sich gern per E-Mail an Prof. Dietzfelbinger wenden.

Weitere Literaturvorschläge

  • I. Wegener, Komplexitätstheorie – Grenzen der Effizienz von Algorithmen, Springer, 2003.
  • G. Ausiello et al., Complexity and Approximation, Springer, 1999.
  • M. Garey, D. Johnson, Computers and Intractability, W.H. Freeman and Co., 1979.
  • C. Papadimitriou, Computational Complexity, Addison-Wesley, 1995.
  • O. Goldreich, Computational complexity - a conceptual perspective, Cambridge University Press, 2008.