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 .
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 .
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
.
Details zum Beweis der beiden Zeithierarchie-Sätze findet sich
in Kapitel 4.2.1 des Buchs .
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
.
- 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
.
- 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
.
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
.
Details zum Thema "Crossing-Sequenzen" und ein Beweis von Satz
4.28 (bzw. von einzelnen Zwischenbehauptungen davon) finden
sich in den Büchern ,
und .
- 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
.
Details zu den Klassen ATIME(T(n)) und ASPACE(S(n)) finden
sich in den Büchern und
.
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
.
Details zum Thema Schaltkreiskomplexität finden sich
im Buch .
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
.
Details zum Thema Schaltkreiskomplexität finden sich
im Buch .
- 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 .
Seiten 247-253 von Kapitel 11 des Buchs .
- 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 .
- 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 .
- 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 .