13.10.2008: Ueberblick ueber den Inhalt, Organisatorisches. Def. k-Band Turingmaschine, Berechnung, Akzeptormaschine. Beispiel aus BC: Maschine zur Erkennung der Sprache 0^n1^n. 16.10.2008: Zeitkomplexitaet TIME_T(x) einer TM T. Zeitkonstruierbare Funktionen. Die Klasse TIME(f(n)) fuer zeitkonstruierbares f. Speedup Theorem. Zeithierarchiesatz: f zeitkonstruierbar: TIME(f(n)) ist *echt* enthalten in TIME(n^2*(f(n))^2). Gap-Theorem: die Einschraenkung "zeitkonstruierbar" ist wirklich erforderlich (ohne Beweis). 20.10.2008: Die Klassen P,NP,E,NE,EXP,NEXP. Bekannte Beziehungen zwischen diesen. P=NP => E=NE durch Padding. Charakterisierung von NP durch polynomielle Verifizierbarkeit. 23.10.2008: Faellt aus. 27.10.2008: Definition FP (in polynomieller Zeit berechenbare Funktionen). Definition NP-vollstaendig, Satz von Cook-Levin (SAT ist NP-vollstaendig). Beispiele NP-vollstaendiger Probleme ohne Beweis. Satz von Ladner (Wenn P =/= NP, dann gibt es Probleme in NP \ P, die doch nicht NP-vollstaendig sind.). Beweis nur angefangen, naechstes Mal detailliert. 30.10.2008: Satz von Ladner, s.o.: Die im Vortrag ausgelassene Aufzaehlung aller NP-vollst Sprachen ist nunmehr ins Skript eingearbeitet. 03.11.2008: Definition Orakel-Turingmaschinen, Definition der relativierten Klassen P^C und NP^C fuer Sprachen C. Veranschaulichung von P^SAT und NP^SAT. Satz: es gibt Sprache C sodass P^C=NP^C. 06.11.2008: Faellt aus 10.11.2008: Konstruktion eines Orakels C sodass P^C =/= NP^C. Definition der Polynomiellen Hierarchie (PH). Charakterisierung der PH durch quantifizierte Praedikate in P. 13.11.2008: Wdh PH. Selbstreduzierbarkeit von SAT; Satz von Karp-Lipton: Falls polynomiell grosse Schaltkreise fuer SAT existieren, so folgt Sigma^P_2=Pi^P_2 also ein Kollaps der polynomiellen Hierarchie. Definition Platzkomplexitaet. 17.11.2008: Definition platzkonstruierbare Funktion. Definition DSPACE(s(n)), NSPACE(s(n)), LOGSPACE=DSPACE(log(n)), NLOGSPACE=NSPACE(log(n)), PSPACE=DSPACE(poly(n)). Folgerung aus Platzhierarchiesatz (wurde weder formalisiert, noch bewiesen): LOGSPACE ist echt enthalten in PSPACE. Typische Probleme in LOGSPACE, NLOGSPACE, PSPACE. Beziehungen zwischen Platz und Zeit (ohne Beweis). Satz von Savitch: NSPACE(s(n)) enthalten in DSPACE(s(n)^2) mit ausfuehrlichem Beweis. Satz von Immerman-Szelepcsenyi: co-NSPACE(s(n)) enthalten in NSPACE(s(n)). Aussage erlaeutert, Beweis naechstes Mal. 20.11.2008: Beweis des Satzes von Immerman-Szelepcsenyi. Platzbeschraenkte Turingmaschinen mit Stack als besonderes Arbeitsband. Definition der Klasse NSPACE(s(n))+STACK. Satz von Cook: NSPACE(s(n))+STACK = DTIME(2^{O(s(n))}). Beweis der Richtung von links nach rechts. Rueckrichtung naechstes Mal. 24.11.2008: Satz von Cook fertig. E/A-Turingmaschinen (Transducer). LOGSPACE Reduktionen. Transitivitaet von LOGSPACE Reduzierbarkeit. NLOGSPACE-Vollstaendgkeit, P-vollstaendigkeit. REACH ist NLOGSPACE-vollst, HORN ist P-vollstaendig. Letzteres o Bew. 27.11.2008: faellt aus. 01.12.2008: Wdh. HORN, Beweis der P-Vollstaendigkeit von HORN. Wdh. PSPACE und Saetze ueber Platzkomplexitaet (Savitch, Immerman-Szelepcsenyi, Cook). Def.: QBF (quantifizierte Boole'sche Formeln). PSPACE-vollstaendigkeit von QBF. 04.12.2008: Beschraenkte Notationsrekursion, Satz von Cobham. Sichere Rekursion nach Bellatoni Cook. 08.12.2008: Sichere Rekursion nach Bellantoni-Cook: Wdh Def., Korrektheit fuer P. LFPL Def. und Bsp. 11.12.2008: LFPL weitere Bsp, Komplexitaetsaussagen zu LFPL ohne Bew. Miller-Rabin Primzahltest. 15.12.2008: Probabilistischer Test, ob ein multivariates Polynom identisch Null ist durch Einsetzen von Zufallswerten. Analyse mithilfe von Schwarz-Zippel Lemma. Anwendung: Test auf perfektes Matching mit Satz von Tutte. 18.12.2008: Beweis Satz von Tutte. Monte-Carlo und Las Vegas Algorithmen. Probabilistische Turingmaschinen. Definition der Klassen PP, R, co-R, BPP, ZPP. 22.12.2008: Wahrscheinlichkeitsverstaerkung fuer R, co-R und BPP. Anwendung: BPP ist enthalten in P/poly. Ausblick auf Derandomisierung: Pseudozufallsgeneratoren und deren Verwendung zur Derandomisierung. Satz von Nisan-Wigderson-Impagliazzo: Wenn E nicht enthalten in P/poly, dann folgt P=BPP. (ohne Beweis) 08.01.2009: Interaktive Beweissysteme, die Komplexitaetsklassen DIP und IP. Gezeigt, dass DIP=NP und IP enthalten in PSPACE. Gezeigt, dass es in IP moeglich ist, zu entscheiden, ob zwei Graphen nicht isomorph sind. 12.01.2009: IP Protokoll fuer co-3SAT mithilfe von Arithmetisierung. 15.01.2009: Erweiterung auf IP Protokoll fuer QBF. PSPACE=IP. Den Artikel "Algebrization: A New Barrier in Complexity Theory" von Aaronson und A Wigderson vorgestellt. Die Klassen PCP und PCP(f(n),g(n)) definiert. 19.01.2009: Beweis, dass NP <= PCP(poly(n),1) begonnen: Arithmetisierung von 3KNF ueber Z/2Z, Struktur des PCP-Protokolls, Satz ueber den Linearitaetstest zur Haelfte bewiesen. Auf der Homepage der Vorlesung wurden zwei ASCII Notizen zu IP und PCP eingestellt. 22.01.2009: Beweis von NP<=PCP(poly(n),1) fertiggestellt. 26.01.2009: Schaltkreiskomplexitaet. Definition von Berechnung mit Schaltkreisfamilien. Die Klassen AC(k) und NC(k). Die Paritaetsfunktion PARITY. Beweis, dass PARITY in NC(1). Begonnen, den Satz von Furst, Saxe und Sipser: PARITY nicht in AC(0) zu beweisen. Der Vortrag folgt dem Buch von Schoening (Perlen der Theoretischen Informatik). Eine ASCII Notiz wird demnaechst eingestellt. 29.01.2009: Beweis des Satzes von Furst-Saxe-Sipser fertiggestellt. ASCII Notiz befindet sich auf der Homepage. 02.02.2009: Parity nicht in AC0 mit polynomieller Approximation nach Razborov und Smolensky. ASCII Notiz befindet sich auf der Homepage. 05.02.2009: ...fertiggestellt. AC0 Reduktion. Folgerung: MAJORITY nicht in AC0. Ausblick auf Arbeitsgebiete der LFE.