| Nr. | Datum | Stoff |
| 1 | 14.10.02 | Skript bis Seite 11, bis Satz von Ben-Or inklusive. |
| 2 | 16.10.02 | S. 11, Satz von Ben-Or, bis Satz 2.3.4 auf S. 14.
|
| 3 | 21.10.02 | S. 14 Satz 2.3.4 bis S. 19 unten im Skript |
| Hinweis: In Kapitel 4 habe ich die Reihenfolge in der Vorlesung ein wenig umgestellt. | ||
| 4 | 23.10.02 | Aus dem Buch Satz 3.2.7 bewiesen sowie
Kapitel 3.3 im Schnelldurchgang (als Wiederholung
des GTI-Stoffs). Viele der vorkommenden Probleme
definiert: Clique, BPP, KP, SAT, 3SAT, HC, DHC, TSP, PARTITION,
VC, IP, etc.
Skript: S. 19 unten bis 21 inkl. Dann Kapitel 4.2 (S. 24 bis 26 oben). |
| 5 | 28.10.02 | Skript S. 26 beendet, S. 27 ohne MED. S. 22 bis S. 24 (Ende von Kap. 4.1). Mit MP3 begonnen (S. 33). |
| 6 | 30.10.02 | MP3 beendet, Minimum Tardiness Sequencing, Boolean Sums, Sequencing with Intervals. Im Skript sind das die Seiten 33-35 sowie 28 und 30-32. (Die Reduktionen/Sätze, die im Skript mit (*) markiert sind, wurden dabei weggelassen.) |
| 7 | 04.11.02 | Minimum Test Collection, Beweis, dass 2SAT in P, Färbbarkeitsproblem definiert, GC2 <=_p 2SAT, begonnen mit dem Beweis, dass GC3 NP-vollst. ist. |
| 8 | 06.11.02 | GC3-Beweis beendet sowie die Beweise für D<=4, G planar, G planar und D<=4, also: Skript S. 38-43 oben. (Dabei die Def. von MAXCUT nicht gemacht (S. 41 oben)) |
| 9 | 11.11.02 | Def. Zahlproblem, Bsp. Zahlprobleme, Begriff pseudopolynomiell, starke NP-Vollständigkeit, Konsequenzen, wenn Problem stark NP-vollständig ist, TSP ist stark NPV, Definition 3-PARTITION, 4-PARTITION und begonnen mit dem Beweis, dass 4-PARTITION stark NPV ist. Im Skript ist das Kapitel 5.3 und im Buch Kapitel 3.5. |
| 10 | 13.11.02 | Den Beweis für 4-PARTITION beendet (S. 44, 45 im Skript). Der Beweis für 3-PARTITION, also der Beweis für Satz 5.4.3, ist nicht Bestandteil der Vorlesung. Kapitel 5.5: Mit dem Beweis von Satz 5.5.2 begonnen. (S.48). |
| 11 | 18.11.02 | S. 48-50 im Skript. Beginn mit Kapitel 6.1 aus dem Skript (S.51), also Buch Kapitel 3.6. (Def. Suchproblem, wann realisiert ein Algorithmus eine Relation, Definition Orakel-Turingmaschine.) |
| 12 | 20.11.02 | Definition Turing-Reduktion, NP-hart, NP-leicht, NP-äquivalent, Eigenschaften der Begriffe (m.a.W.: Kap. 3.6 Buch beendet). S. 51-52 im Skript. Begonnen mit einleitenden Worten zum Beweis, dass Primzahltest in Polynomialzeit möglich ist. |
| 13 | 25.11.02 | Primzahltest ist in P. Von meinem Aufschrieb (abrufbar unter Begleitmaterial) dazu bis Seite 9 Mitte (der komplette Beweis der Rechenregel III) inkl.) |
| 14 | 27.11.02 | In meinem Primzahltest-Aufschrieb bis Seite 15 inkl. Hauptsatz. |
| 15 | 02.12.02 | Primzahltest beendet. Im Aufschrieb von mir die Seiten 16 bis 20 inkl. |
| 16 | 04.12.02 | Klasse co-NP und polynomielle Hierarchie: S. 53 bis 56 inklusive, (also auch, wie im Skript vermerkt, Buch S. 81-83 mit SAT* und MEC und Aussagen darüber). Von S. 57 Skript Korollar 7.3.13 sowie die Aussage von Satz 7.3.12 (Beweis am Mo.) |
| 17 | 09.12.02 | S. 57 bis 60 Mitte im Skript. Aus dem Buch also auch die Definitionen der verschiedenenen probabilitischen Klassen etc. (Kapitel 3.8). Begonnen mit den Aussagen der Chernoffschranken. |
| 18 | 11.12.02 | Chernoffschranke beendet (=Skript 60/61), sowie Buch Kapitel 3.8:
Amplifikation für BPP-Maschinen, Nachweis
von P subset ZPP subset RP subset BPP subset PP, Beweis von RP subset NP,
ZPP = co-RP geschnitten RP, sowie begonnen mit dem Beweis, dass
NP vereinigt co-NP in PP enthalten ist: Nachgewiesen, dass eine probab.
TM M mit polynomieller Rechenzeit und der Eigenschaft, dass: w aus L ==> Prob(M(w)=1) >= 1/2^f(n) für ein Polynom f w nicht aus L ==> Prob(M(w)=1) = 0. beweist, dass die Sprache L in PP ist. |
| 19 | 16.12.02 | Beweis, dass NP vereinigt co-NP Teilmenge von PP, Beweis von BPP Teilmenge von Sigma2 geschnitten Pi2. Übersicht über den Zoo der probabilistischen Komplexitätsklassen. Begonnen mit Kapitel 9: Interaktive Beweise etc. Am Beispiel des "Pumpinglemmas". |
| 20 | 18.12.02 | Interaktive Beweissysteme definiert, IP, IP(k), GIquer in IP(2),
BP(NP) in Pi2, BP(NP) in IP(2), begonnen mit dem Beweis, dass
GIquer in BP(NP) ist: also Varianz einer 01-Zufallsvariablen,
Nachweis, dass W*a = b für alle b die W'keit 2^-k hat, wenn a ungleich 0. Kurz: 66-69 im Skript sowie Teile von S. 70 unten bis 71 oben. Die Aussage BP(NP) Teilmenge von Pi2 ist versteckt in den letzten fünf Zeilen des Beweises auf S. 73. |
| 21 | 06.01.03 | Beweis beendet, dass GIquer in BP(NP) liegt. Begonnen mit dem Beweis, dass die polynomielle Hierarchie zusammenbräche, wenn GI NP-vollständig wäre. Im Skript: S. 70-S.72, Zeile 7 von unten. |
| 22 | 08.01.03 | Beweis zu Satz 9.2.5 beendet. Zero-Knowledge-Beweissysteme, und zwar solche mit PZKE (perfekter Zero-Knowledge-Eigenschaft) und CZKE (Computational Zero-Knowledge-Eigenschaft). CZKE etwas ausführlicher diskutiert als im Skript. Also: S. 72-75 komplett. |
| 23 | 13.01.03 | Wie benutzt man Einwegfunktionen für Bit Commitment. HC hat Beweissysteme mit CZKE. Definition von PCP(r(n),q(n)), was ist PCP(0,*), PCP(*,0), PCP(0,0), Aussage des PCP-Theorems PCP(logn,1)=NP. Kapitel Approx.algorithmen: Def. Optimierungsproblem, worst-case-Güte, asymptot. worst-case-Güte, Bsp. für Unterschied. Also: Skript, S. 76-79, ohne Lemma 9.4.4 und Korollar 9.4.5. Mit S. 82 begonnen, also S. 68 und 69 im Buch. |
| 24 | 15.01.03 | Def. der Approx.güte von Problemen, PAS, FPAS, additiver Fehler, VC kann mit Güte 2 approx. werden, die üblichen Reduktionen machen bei Opt.problemen keinen Sinn, Def. APX-reduzierbar. APX-hart, APX-vollständig. Falls P ungleich NP, dann: gibt es keinen Approx.algo mit addit. Fehler für das Rucksackproblem, keinen für "IP_max", stark NP-harte Probleme haben kein FPAS, Aussage: Wenn bestimmte Entscheidungsprobleme NP-hart sind, dann hat das entsprechende Opt.problem kein PAS, zB COLORING. Also: Skript S. 82-S. 85 Mitte inklusive der dort erwähnten Buchseiten. |
| 25 | 20.01.03 | Beweise zu Nichtapproximierbarkeit von COLORING (worst-case Güte bzw. asymptotische wc-Güte), Bin Packing, TSP, APX-Algorithmen für MAXSAT und MAX3SAT (etwas andere als die im Skript), skizziert, wie man geeignete Transformation "mit Lücke" verwenden kann, um Approx.probleme als NP-hart nachzuweisen, begonnen mit dem Beweis, dass man mit Hilfe des PCP-Theorems eine solche Transformation "mit Lücke" angeben kann, Verifzierer mit Hilfe von Booleschen Funktionen kodiert. Also: Skript S. 85-87 Mitte sowie 88 unten bis 90 Mitte. |
| 26 | 22.01.03 | Die "Transformation mit Lücke" fur MAX3SAT beendet, Korollar für
APX-harte Probleme, Clique ist nicht in APX bewiesen,
begonnen mit Kapitel 11 (nicht "10" wie in der Vorlesung geschrieben),
also Komplexitätsklassen für Speicherplatzbedarf. Modellierung
diskutiert, Verwendung von "Spuren", Def. DTAPE, NTAPE, PSPACE, NSPACE,
Konfigurationen gezählt, um Speicherplatz s(n) ==> Zeitschranke ...
zu erhalten, NP Teilmenge PSPACE. Also: Skript S. 90 sowie 94 oben (im Buch mit Kapitel 5.4 begonnen). |
| 27 | 27.01.03 | L kontextsensitiv <=> L in DTAPE(n), Normalform für kontexts. L. Satz von Savitch durch Angabe von rekursiver Prozedur bewiesen. PH subset PSPACE, Def. PSPACE-vollständig, Def. QBF, Begonnen mit dem Beweis, dass QBF PSPACE-vollständig ist: Nachgewiesen, dass QBF in PSPACE. Also: Im Skript: S.94 bis 97 unten (inkl. Buch S. 140/141). |
| 28 | 29.01.03 | Beweis, dass QBF PSPACE-vollständig ist, beendet. Einige Beispiele für Probleme, die auch PSPACE-vollständig sind, ohne Beweis aufgelistet. Satz von Immerman/Szelepcsenyi erläutert und bewiesen. Hier empfehle ich den Link auf eine Vorlesung in Cornell , dort wird der Satz in der Art bewiesen, wie ich das in der Vorlesung getan habe. Also: Skript S. 97 unten bis 100 unten (inkl. dem Beweis von Immerman/Szelepcsenyi, der im Buch Satz 5.4.9 ist). Allerdings den Beweis zu "CSL ist PSPACE-vollständig" ausgelassen. |
| 29 | 03.02.03 | In dieser Vorlesung wurde ich von Philipp Wölfel vertreten. Nichtuniforme Komplexitätsklassen: Schaltkreise und Simulationen von Turingmaschinen durch Schaltkreise. Also: Im Skript Kapitel 13 bis 13.2 inklusive komplett. |
| 30 | 05.02.03 | nichtuniforme TM definiert, zwei Simulationen von Schaltkreisen durch nichtuniforme TMs vorgeführt. Fazit gezogen: Beziehung SK-Größe/Zeit von nicht-uniformen TMs bzw. SK-Tiefe/TM-Platz. Definition uniforme Schaltkreise, nichtuniforme Komplexitätsklassen definiert, begonnen mit dem Beweis, dass P-SIZE = P/Poly ist. Also: Im Skript: S. 111 ab Kapitel 13.3, bis 115 unten. |
| 31 | 10.02.03 | Beweis P-SIZE=P/Poly beendet. Charakterisierung von NP/Poly
NICHT gemacht. BPP Teilmenge von P/Poly bewiesen,
Resultat, dass aus SAT in P/Poly folgt, dass Sigma_2=Sigma_3,
ohne Beweis erwähnt, aber: polynomielle Selbstreduzierbarkeit definiert,
gezeigt, dass SAT polynomiell selbstreduzierbar ist.
Begonnen mit Kapitel 14: untere Schranken für Schaltkreise, 2n-3-Schranke
für Thresholdfunktion gezeigt, Branchingprogramme (BPs) definiert,
begonnen mit einer fast quadratischen unteren Schranke für BPs:
gezählt, wieviele Funktionen in BPs mit s Knoten berechnet werden können.
Also: Im Skript: S. 115 beendet, 117, 118 bis Mitte, Satz von 119 erwähnt ohne Beweis, Definition von BPs von Seite 121, 123, 124 bis Mitte ca. |
| 32 | 12.02.03 | Methode von Nechiporuk für Formeln und BPs beendet, Subfunktionen bei Funktion ISA gezählt und zugehörige Schranke bewiesen. Klassen NC^k, AC^k bzw. NC, AC, AC^0,d definiert und die "Verzahnung" der NC-AC-Hierarchie bewiesen. Also: Im Skript: 124-127 inkl. |