Aktueller Eintrag

Logbuch: Komplexitätstheorie

Vorlesung  im SoSe 2011

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, die in der Vorlesung verwendeten Folien und gelegentlich ergänzende Bemerkungen.

Vorsicht: In der Vorlesung und der Übung werden viele wichtige Dinge (insbesondere Beweise, aber auch einiges andere) an der Tafel erklärt. Diese Dinge sind für die Veranstaltung "Komplexitätstheorie" wesentlich und daher auch dann prüfungsrelevant, wenn sie nicht in den hier erhältlichen pdf-Dateien der Vorlesungsmitschriften enthalten sind.


Di, 12.04.2011
Kapitel 0: Einleitung und grundlegende Notationen (Beispiele für Berechnungsprobleme; Ziele der Komplexitätstheorie; Notationen; Repräsentation von Objekten durch Worte; Entscheidungsprobleme und Sprachen; die O-Notation);
Organisatorisches (siehe Angaben auf der Webseite der Vorlesung);
Beginn mit Kapitel 1: Das Berechnungsmodell - und warum Details der Definition nicht wichtig sind (heute: k-Band Turingmaschinen; Beispiel-TM zum Erkennen von Palindromen; Einführung des Begriffs "M berechnet eine Funktion f in T(n) Schritten"; Zeitkonstruierbarkeit).
Vorlesungsmitschrift:
Skript, Seiten 1-20.
Weitere Lektüre:
Introduction, Kapitel 0, und Seiten 9-16 von Kapitel 1 des Buchs [AB] .
Kapitel 5 (P, NP und die NP-Vollständigkeit) von Prof. Georg Schnitgers Skript zur Vorlesung Algorithmentheorie.
Di, 19.04.2011
Abschluss von Kapitel 1: Das Berechnungsmodell - und warum Details der Definition nicht wichtig sind (heute: Varianten von TMen und effiziente Simulationen, eine universelle Turingmaschine, Unentscheidbarkeit und Diagonalisierung, der Begriff DTIME(T(n)) und die Klasse P).
Beginn mit Kapitel 2: NP und NP-Vollständigkeit (heute: Definition der Klassen NP und EXP, nichtdeterministische Turingmaschinen (kurz: NDTM), der Begriff NTIME(T(n)), Polynomialzeit-Reduzierbarkeit, NP-Härte und NP-Vollständigkeit, ein Beispiel für eine NP-vollständige Sprache: TMSAT).
Übungsblatt 1 ausgeteilt.
Vorlesungsmitschrift:
Skript, Seiten 21-45.
Weitere Lektüre:
Kapitel 1 sowie Seiten 38-44 von Kapitel 2 des Buchs [AB] .
Kapitel 5 (P, NP und die NP-Vollständigkeit) und 6 (NP-vollständige Probleme) von Prof. Georg Schnitgers Skript zur Vorlesung Algorithmentheorie.
Di, 26.04.2011
Abschluss von Kapitel 2: NP und NP-Vollständigkeit (heute: Nachweis der NP-Härte der Sprache TMSAT, eine Sammlung NP-vollständiger Probleme, Entscheidungsprobleme vs. Suchprobleme, coNP, EXP und NEXP, Nachweis, dass aus "EXP ungleich NEXP" auch "P ungleich NP" folgt (Methode: "padding")).
Beginn mit Kapitel 3: Diagonalisierung (heute: zwei Zeithierarchie-Sätze (für DTIME und für NTIME), Folgerungen: "P ungleich EXP" und "NP ungleich NEXP").
Übungsblatt 2 ausgeteilt.
Vorlesungsmitschrift:
Skript, Seiten 45-65.
Weitere Lektüre:
Kapitel 2 sowie Seiten 68-71 von Kapitel 3 des Buchs [AB] .
Details zum Beweis der beiden Zeithierarchie-Sätze findet sich in Kapitel 4.2.1 des Buchs [G] .
Ein Einblick in die historische Entwicklung der Theorie der NP-Vollständigkeit wird in Richard M. Karps Turing Award Lecture gegeben (1985, anlässlich der Verleihung des "ACM Turing Awards" an Richard M. Karp).
Di, 03.05.2011
Nachtrag zu Kapitel 2: der Satz von Berman
Abschluss von Kapitel 3: Diagonalisierung (heute: der Satz von Ladner; Orakel-TM und der Satz von Baker, Gill und Solovay; die Grenzen der Diagonalisierung).
Beginn mit Kapitel 4: Platzkomplexität (heute: die Klassen SPACE(S(n)) und NSPACE(S(n)); Platzkonstruierbarkeit; Konfigurationsgraphen; einfache Relationen zwischen Zeit- und Platzklassen).
Übungsblatt 3 ausgeteilt.
Vorlesungsmitschrift:
Skript, Seiten 66-83.
Weitere Lektüre:
Kapitel 3 sowie die Seiten 78-81 von Kapitel 4 des Buchs [AB] .
Di, 10.05.2011
Weiter mit Kapitel 4: Platzkomplexität (heute: Bemerkung (ohne Beweis) dazu, DTIME(S(n)) in SPACE(S(n)/log(S(n))) enthalten ist; die Platzklassen L, NL, POLYLOGSPACE, PSPACE, NPSPACE; Beispiele für platzbeschränkte Berechungen; lineare Kompression und Platzhierarchiesatz; der Satz von Savitch (inkl. Folgerung, dass PSPACE = NPSPACE); PSPACE-Vollständigkeit von TQBF; Anmerkungen zum Bezug zwischen PSPACE-Vollständigkeit und der Existenz von Gewinnstrategien in 2-Personen-Spielen; logspace-berechenbare Funktionen).
Übungsblatt 4 ausgeteilt.
Vorlesungsmitschrift:
Skript, Seiten 84-99.
Weitere Lektüre:
Seiten 81-88 von Kapitel 4 des Buchs [AB] .
Di, 17.05.2011
Weiter mit Kapitel 4: Platzkomplexität (heute: logspace-Reduzierbarkeit und NL-Vollständigkeit; NL-Vollständigkeit des Problems PATH; der Satz von Immerman und Szelepcsényi; Bezüge zwischen Platzklassen und der Chomsky-Hierarchie; kurze Einführung in den Begriff der "Crossing-Sequenzen"; Überblick über die Inklusionsstruktur der bisher betrachteten Komplexitätsklassen).
Übungsblatt 5 ausgeteilt.
Vorlesungsmitschrift:
Skript, Seiten 99-110 und 115-117.
Weitere Lektüre:
Seiten 88-93 von Kapitel 4 des Buchs [AB] .
Ein detaillierter Überblick über einige der in der Forschung betrachteten Komplexitätsklassen findet sich hier.
Di, 24.05.2011
Abschluss von Kapitel 4: Platzkomplexität (heute: Beweis von Satz 4.28 (SPACE(o(log log n) enthält nur reguläre Sprachen) unter Verwendung von "Crossing-Sequenzen").
Beginn mit Kapitel 5: Die Polynomialzeit-Hierarchie und Alternierungen (heute: Definition der PH und der k-ten Stufe der PH; Beispiele für Probleme in der 2-ten Stufe der PH; Überblick über die Inklusionsstruktur der Stufen der PH; vollständige Probleme für einzelne Stufen der PH; PH vs. PSPACE).
Übungsblatt 6 ausgeteilt.
Vorlesungsmitschrift:
Skript, Seiten 110-115 und 118-129.
Weitere Lektüre:
Seiten 95-99 von Kapitel 5 des Buchs [AB] .
Details zum Thema "Crossing-Sequenzen" und ein Beweis von Satz 4.28 (bzw. von einzelnen Zwischenbehauptungen davon) finden sich in den Büchern [K] , [S] und [HU] .
Di, 31.05.2011
Weiter mit Kapitel 5: Die Polynomialzeit-Hierarchie und Alternierungen (heute: Charakterisierung der Stufen der PH durch Orakel Turingmaschinen; alternierende Turingmaschinen (ATM); die Klassen ATIME(T(n)) und ASPACE(S(n)); Bezüge zwischen diesen Klassen und deterministischen bzw. nichtdeterministischen Zeit- und Platzklassen: AL = P, AP = PSPACE, APSPACE = EXP, AEXP = EXPSPACE; die Klassen ΣkTIME(poly(n)) und ΠkTIME(poly(n)) und deren Bezug zur k-ten Stufe der PH; die Zeit-Platz-Klasse TISP(T(n),S(n)) und deren Bezug zu Alternierungen; ein Zeit-Platz-Tradeoff: NTIME(n) ist nicht in TISP(n1,2,n0,2) enthalten).
Übungsblatt 7 ausgeteilt.
Vorlesungsmitschrift:
Skript, Seiten 129-145.
Weitere Lektüre:
Seiten 99-104 von Kapitel 5 des Buchs [AB] .
Details zu den Klassen ATIME(T(n)) und ASPACE(S(n)) finden sich in den Büchern [K] und [P] .
Ein Überblick über Zeit-Platz Tradeoffs wird in Dieter van Melkebeeks Artikel A Survey of Lower Bounds for Satisfiability and Related Problems (Foundations and Trends in Theoretical Computer Science, 2: 197-303, 2007) gegeben.
Di, 07.06.2011
Abschluss von Kapitel 5: Die Polynomialzeit-Hierarchie und Alternierungen (heute: Nachweis, dass NTIME(n) nicht in TISP(n1,2,n0,2) enthalten ist und dass SAT nicht in TISP(n1,1,n0,1) liegt).
Beginn mit Kapitel 6: Boolesche Schaltkreise (heute: grundlegende Definitionen, Beispiel, 2 Sätze von Shannon über die Größe von Schaltkreisen für n-stellige Boolesche Funktionen: Θ(2n/n), die Klasse SIZE(S(n)), nichtuniformer Hierarchiesatz, die Klasse P/poly)
Übungsblatt 8 ausgeteilt.
Vorlesungsmitschrift:
Skript, Seiten 145-163.
Weitere Lektüre:
Kapitel 5 sowie Seiten 106-109 und 115-116 von Kapitel 6 des Buchs [AB] .
Details zum Thema Schaltkreiskomplexität finden sich im Buch [V] . Der Beweis des o.g. Resultats bzgl. TISP(T(n),S(n)), NTIME(n) und SAT findet sich im Artikel Time-Space Lower Bounds for Satisfiability von L. Fortnow, R. Lipton, D. van Melkebeek und A. Viglas (Journal of the ACM, 52: 835-865, 2005).
Di, 14.06.2011
Weiter mit Kapitel 6: Boolesche Schaltkreise (heute: Beweis des nichtuniformen Hierarchiesatzes; Nachweis, dass P in P/poly enthalten ist; Beweis des Satzes von Karp und Lipton, der besagt, dass NP nicht in P/poly enthalten ist, es sei denn, die Polynomialzeit-Hierarchie kollabiert; Nachweis, der P-Vollständigkeit des Problems CIRCUIT-EVAL und der NP-Vollständigkeit des Problems CIRCUIT-SAT; Charakterisierung der Klasse P/poly durch Polynomialzeit-Turingmaschinen mit polynomiell langem "Advice"; P-uniforme und logspace-uniforme Schaltkeisfamilien; Nachweis, dass P = logspace-uniformes P/poly = P-uniformes P/poly; Nachtrag zu Kapitel 5: Nachweis, dass DTIME(T(n)) in ASPACE(log T(n)) enthalten ist (für zeitkonstruierbares T mit T(n)>n)).
Ein Übungsblatt wurde heute nicht ausgeteilt.
Vorlesungsmitschrift:
Skript, Seiten 160-161 und 164-177.
Weitere Lektüre:
Seiten 109-114 von Kapitel 6 des Buchs [AB] .
Details zum Thema Schaltkreiskomplexität finden sich im Buch [V] .
Di, 21.06.2011
Abschluss von Kapitel 6: Boolesche Schaltkreise (heute: die Klassen NCi, ACi, NC als Modelle für effiziente parallele Berechnungen; Beispiele: PARITY in NC1, PATH in AC1; Nachweis, dass die Klasse NL in logspace-uniformem AC1 enthalten ist; der Satz von Furst, Saxe, Sipser bzw Ajtai, der besagt, dass PARITY nicht in AC0 liegt (ohne Beweis)).
Beginn mit Kapitel 7: Randomisierte Berechnungen (heute: ein probabilistischer Primzahltest).
Übungsblatt 9 ausgeteilt.
Vorlesungsmitschrift:
Skript, Seiten 178-193.
Weitere Lektüre:
Seiten 116-119 von Kapitel 6 sowie Seiten 128-129 von Kapitel 7 des Buchs [AB] .
Seiten 247-253 von Kapitel 11 des Buchs [P] .
Di, 28.06.2011
Weiter mit Kapitel 7: Randomisierte Berechnungen (heute: probabilistische Turingmaschinen; die Klassen RP, coRP, ZPP, BPP; Wahrscheinlichkeitsverstärkung für RP und für BPP; Nachweis, dass ZPP der Durchschnitt von RP und coRP ist; Nachweis, dass BPP in P/poly enthalten ist).
Ein Übungsblatt wurde heute nicht ausgeteilt.
Vorlesungsmitschrift:
Skript, Seiten 194-210.
Weitere Lektüre:
Seiten 123-126 und 131-136 von Kapitel 7 des Buchs [AB] .
Do, 30.06.2011
Abschluss von Kapitel 7: Randomisierte Berechnungen (heute: Nachweis, dass BPP in der zweiten Stufe der Polynomialzeit-Hierarchie enthalten ist (Lautemann-Methode); Anmerkungen zur Suche nach vollständigen Problemen und Hierarchiesätzen für BPP; randomisierte platzbeschränkte Berechnungen: die Klassen BPL und RL; der Random-Walk-Algorithmus zum Nachweis, dass UPATH in RL liegt).
Übungsblatt 10 wird in der am nächsten Dienstag stattfindenden Übungsstunde ausgeteilt.
Vorlesungsmitschrift:
Skript, Seiten 211-220.
Weitere Lektüre:
Seiten 136-141 von Kapitel 7 des Buchs [AB] .
Di, 12.07.2011
Kapitel 8: Der PCP-Satz (heute: der PCP-Satz (Approximations-Sicht; ohne Beweis), (Nicht-)Approximierbarkeit von MAX-3SAT, probabilistisch überprüfbare Beweise, (r(n),q(n))-PCP-Verifizierer, Graph-Nicht-Isomorphie, die Komplexitätsklasse PCP(r(n),q(n)), der PCP-Satz (PCP-Sicht; ohne Beweis), Folgerung: "new shortcut for long math proofs").
Überblick über die in der Veranstaltung "Komplexitätstheorie" betrachteten Komplexitätsklassen (und einige vollständige Probleme).
Ein Übungsblatt wurde heute nicht ausgeteilt.
Vorlesungsmitschrift:
Skript, Seiten 221-235.
Weitere Lektüre:
Seiten 237-244 von Kapitel 11 des Buchs [AB] .