Professur für
Theoretische Informatik

Herzlich willkommen zur Veranstaltung Komplexitätstheorie! In diesem Semester findet die Vorlesung online statt: Jede Woche erscheinen Videos, die Sie hier im Logbuch finden.

• Einführung
  Inhaltsangabe, Organisatorisches
  Referenzen:
  • Folien: Einführung (1-8) [ Druckversion | Bildschirmversion ]
    
  • S. Arora und B. Barak, Computational Complexity, a Modern Approach (Draft), Cambridge University Press, 2009.
  • M. Sipser, Introduction to the Theory of Computation, Paperback 3rd edition, Cengage Learning, 2012.
  [Direktlink] [Youtube] (Video aktualisiert am 20.04.2020)
  

• Laufzeit
  Average-Case-Komplexität: Verteilungsprobleme, polynomielle erwartete Laufzeit, AvgP, AvgNP bzw. DistNP , Bounded Halting, Random k-SAT, Bounded-Distance Decoding, Smoothed Complexity (geglättete Komplexität): Killer-Applikationen
  Referenzen:
  • Folien: Einführung (9-28) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitt 2.1
    
  • T. Roughgarden, CS264: Beyond Worst-Case Analysis (Lecture 17+18)
  • A. Bogdanov, L. Trevisan, Average-Case Complexity
  [Direktlink] [Youtube]

• Worst-Case-Laufzeit
  Worst-Case-Komplexitätsklassen für die Laufzeit, polynomielle Reduktion, alternierende Berechnungen
  Referenzen:
  • Folien: Einführung (29-39) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitte 2.1 und 2.2
    
  [Direktlink] [Youtube]

• Diagonalisierung und Orakel
  Zeit-konstruierbare Funktionen: die Diagonalierungsmethode von Cantor, eine Zeithierarchie, Orakelberechnungen, P = NP bzw. P ≠ NP in verschiedenen Berechnungswelten
  Referenzen:
  • Folien: Einführung (40-48) [ Druckversion | Bildschirmversion ]
  • Skript: Abschnitt 2.5
    
  [Direktlink] [Youtube]

• Einführung in die Speicherplatzkomplexität
  Speicherplatzklassen (deterministisch, nichtdeterministisch, alternierend), sublogarithmischer und logarithmischer Speicherplatz
  Referenzen:
  • Folien: Speicherplatz (1-17) [ Druckversion | Bildschirmversion ]
    
  Skript: Abschnitt 2.3
  
  • Kapitel 8 in M. Sipser, Introduction to the Theory of Computation, Paperback 3rd edition, Cengage Learning, 2012.
  [Direktlink] [Youtube]

• DL und NL
  determistisch-logarithmischer Platz, nichtdetermistisch-logarithmischer Platz, Logspace-Reduktionen, NL-Vollständigkeit, D-REACHABILITY
  Referenzen:
  • Folien: Speicherplatz (18-30) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 3.2
    
  • Kapitel 8 in M. Sipser, Introduction to the Theory of Computation, Paperback 3rd edition, Cengage Learning, 2012.
  [Direktlink] [Youtube]

• Chomsky-Hierarchie
  von Grammatiken erzeugte Sprachen: reguläre, kontextfreie, kontextsensitive und rekursiv-aufzählbare Sprachen
  Referenzen:
  • Folien: Speicherplatz (31-42) [ Druckversion | Bildschirmversion ]
    
  Skript: Abschnitt 3.4
  
  [Direktlink] [Youtube]

• Satz von Savitch
  Platzkonstruierbarkeit, Diagonalisierung, D-REACHABILITY: nichtdeterministischer Platz s ist in deterministischem Platz s² enthalten
  Referenzen:
  • Folien: Speicherplatz (43-51) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 3.2
    
  • Kapitel 8 in M. Sipser, Introduction to the Theory of Computation, Paperback 3rd edition, Cengage Learning, 2012.
  [Direktlink] [Youtube]

• Satz von Immerman und Szelepcsenyi
  D-UNREACHABILITY, das Anzahl-Problem, nichtdeterministischer Speicherplatz ist unter Komplementbildung abgeschlossen
  Referenzen:
  • Folien: Speicherplatz (52-56) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 3.2
    
  • Kapitel 8 in M. Sipser, Introduction to the Theory of Computation, Paperback 3rd edition, Cengage Learning, 2012.
  [Direktlink] [Youtube]

Zu den Videos über paralleles Rechnen empfehlen wir:

Greenlaw, Hoover und Ruzzo: Limits to parallel computation: P-completeness theory, Oxford University Press, 1995.

• PSPACE
  PSPACE-Vollständigkeit, QBF, AP = PSPACE, QBF ist PSPACE-vollständig, Geographie-Spiel, Zählprobleme
  Referenzen:
  • Folien: Speicherplatz (57-72) [ Druckversion | Bildschirmversion ]
    
  Skript: Abschnitt 3.3
  
  • Kapitel 8 in M. Sipser, Introduction to the Theory of Computation, Paperback 3rd edition, Cengage Learning, 2012.
  [Direktlink] [Youtube]

• Einführung in die Parallelität
  das Modell der Schaltkreise (Größe, Tiefe, Fanin), Größe und Tiefe für die meisten Schaltkreise, Nick's Class, AC
  Referenzen:
  • Folien: Parallelität (1-14) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 2.4
    
  [Direktlink] [Youtube]

• Platz und Laufzeit
  Zusammenhang zwischen Speicherplatz und Tiefe von Schaltkreisen (NC¹ ⊆ DL ⊆ NL ⊆ NC², DEPTH_uniform(s) ⊆ DSPACE(s) ⊆ NSPACE(s) ⊆ DEPTH_uniform(s²), D-REACHABILITY liegt vermutlich nicht in NC¹)
  Referenzen:
  • Folien: Speicherplatz (15-20) [ Druckversion | Bildschirmversion ]
    
  Skript: Abschnitt 4.1
  
  [Direktlink] [Youtube]

• P-Vollständigkeit
  Logspace-Reduktion, Circuit Value ist P-vollständig, die Klasse P/poly, lineare Programmierung ist P-vollständig, Parallelisierbarkeit von Greedy-Algorithmen (Independent Set, LFMIS)
  Referenzen:
  • Folien: Speicherplatz (21-40) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 4.2
    
  • Kapitel 8 in M. Sipser, Introduction to the Theory of Computation, Paperback 3rd edition, Cengage Learning, 2012.
  [Direktlink] [Youtube]

Zu den Videos über randomisiertes Rechnen empfehlen wir:

Avi Wigderson: Lecture on a computational theory of randomness, Youtube.

Avi Wigderson: Randomness – A Computational Complexity View

• BPP
  Komplexitätsklassen für randomisierte Berechnungen (BPP, WeakBPP, StrongBPP, ZPP, RP, coRP, PP), Fehlerreduktion (WeakBPP = StrongBPP), BPP ⊆ P/poly, BPP ⊆ Σ^p₂ ∩ Π^p₂
  Referenzen:
  • Folien: Randomisierte Algorithmen (1-17) [ Druckversion | Bildschirmversion ]
    
  Skript: Abschnitt 7.1
  
  [Direktlink] [Youtube]

• Randomisierte Reduktionen
  Promise-Probleme: Unique-SAT, Isolationsmethode, Zusammenfassung
  Referenzen:
  • Folien: Randomisierte Algorithmen (18-23) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 7.2
    
  [Direktlink] [Youtube]

• One-Way-Funktionen
  vernachlässigbare Funktionen, Definition von One-Way-Funktionen und One-Way-Permutationen, Tests, Familien von One-Way-Funktionen; Wenn es eine One-Way-Funktion gibt, dann ist P ≠ NP; vermutliche One-Way-Funktionen (Faktorisierung, diskreter Logarithmus, Rabin, RSA, Learning-With-Errors (LWE))
  Referenzen:
  • Folien: Kryptographie (1-10) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 8.1
    
  [Direktlink] [Youtube]

Zu den Videos über Kryptographie empfehlen wir:

S. Goldwasser und M. Bellare: Lecture Notes on Cryptography.

• Pseudo-Random-Generatoren
  statistische Tests, Bit-Tests, PRGs aus One-Way-Funktionen, Generator der linearen Kongruenzen, Streckung um ein Bit, Existenz von One-Way-Funktionen und PRGs, One-Way-Permutationen und Hard-Core-Bit, Bit-Commitment, Private-Key-Kryptographie mit One-Time-Pad, Derandomisierung, Satz von Impagliazzo und Wigderson, Fine-Grained-Complexity (ETH und SETH)
  Referenzen:
  • Folien: Kryptographie (12-32) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 8.1.1
    
  [Direktlink] [Youtube]

• Pseudo-Random-Funktionen
  Pseudo-Random-Funktionen aus PRGs, kollisionsresistente Hashfunktionen, Nachrichten-Authentifizierung mit privatem Schlüssel
  Referenzen:
  • Folien: Kryptographie (33-46) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 8.1.2
    
  [Direktlink] [Youtube]

• Natürliche Beweise
  Wieso ist der Nachweis von P ≠ NP so schwierig? Größe und Tiefe von Schaltkreisen, Empfindlichkeit, natürliche Eigenschaften, AC⁰, boolesche PRFs haben keine Schaltkreise polynomieller Größe
  Referenzen:
  • Folien: Natürliche Beweise (1-14) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 8.1.2.1
    
  [Direktlink] [Youtube]

Zu den Videos über Gitter-Kryptographie empfehlen wir:

Chris Peikert: A Decade of Lattice Cryptography.

• Trapdoor-Funktionen
  Public-Key-Kryptographie, Beispiele für Trapdoor-Funktionen (Rabin, RSA, Elgamal), semantische Sicherheit (IND-CPA, IND-CCA1, IND-CCA2), digitale Unterschriften
  Referenzen:
  • Folien: Kryptographie (47-61) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 8.2
    
  [Direktlink] [Youtube]

• Einführung in die Gitter-Kryptographie
  Gitter, Parallelotop/Grundmasche, Eigenschaften von Gittern, Shortest-Vektor-Probleme (SVP, SVP_γ, Gap-SVP_γ, SIVP_γ, CVP)
  Referenzen:
  • Folien: Kryptographie (62-68) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 8.3 (bis exkl. 8.3.1)
    
  • Chris Peikert: A Decade of Lattice Cryptography
  [Direktlink] [Youtube]

• Short Integer Solution
  SIS_n,q,β,m (Lösbarkeit, Diskussion der Parameter, Worst-Case-nach-Average-Case-Reduktion), der SIS-Hauptsatz, SIS liefert kollisionsresistente Hashfunktionen und somit One-Way-Funktionen
  Referenzen:
  • Folien: Kryptographie (69-75) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 8.3.1
    
  • Chris Peikert: A Decade of Lattice Cryptography
  [Direktlink] [Youtube]

• Beweis des SIS-Hauptsatzes
  
  Referenzen:
  • Folien: Kryptographie (76-84) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 8.3.1.1
    
  • Chris Peikert: A Decade of Lattice Cryptography
  [Direktlink] [Youtube]

• Learning with Errors I
  LWE-Suchvermutung, LWE-Entscheidungsvermutung, Average-Case = Worst-Case, LWE-Hauptsatz, LWE-Private-Key-Kryptographie, die Rolle der Verteilung D
  Referenzen:
  • Folien: Kryptographie (85-102) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 8.3.2 bis inkl. 8.3.2.2
    
  • Chris Peikert: A Decade of Lattice Cryptography
  [Direktlink] [Youtube]

• Learning with Errors II
  LWE-Public-Key-Kryptographie, voll-homomorphe Verschlüsselung, Konsequenzen der Kryptographie, Fünf Welten von Impagliazzo (Algorithmica, Heuristica, Pessiland, Minicrypt, Cryptomania), Zusammenfassung
  Referenzen:
  • Folien: Kryptographie (103-111) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 8.3.2.3
    
  • Chris Peikert: A Decade of Lattice Cryptography
  [Direktlink] [Youtube]

• Hilberträume
  mathematische Grundlagen: komplexe Zahlen, inneres Produkt, Hilbertraum, Zustände, Cauchy-Folgen, Hilbert- und Orthonormal-Basis, Prähilbertraum, Dirac-Notation (Bra und Ket), Tensorprodukt, Qubits
  Referenzen:
  • Folien: Quantenalgorithmen (1-16) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 11.1
    
  • Scott Aaronson: Lecture notes! Intro to Quantum Information Science
  • Ronald de Wolf: Quantum Computing: Lecture Notes
  [Direktlink] [Youtube]

• Operatoren und Messungen I
  unitäre Operatoren, Matrixdarstellung, projektive Messungen, Observable, Born-Regel, quantenmechanische Systeme
  Referenzen:
  • Folien: Quantenalgorithmen (17-24) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 11.2
    
  • Scott Aaronson: Lecture notes! Intro to Quantum Information Science
  • Ronald de Wolf: Quantum Computing: Lecture Notes
  [Direktlink] [Youtube]

• Operatoren und Messungen II
  äußeres Produkt, Verschränkung, quantenmechanische und probabilistische Systeme, Interferenz, Qubits: Polarisierung von Photonen, Elektronenspin, Vielteilchen-Systeme, Einstein-Podolsky-Rosen-Paare (EPR-Paare), Messungen in Vielteilchensystemen
  Referenzen:
  • Folien: Quantenalgorithmen (25-37) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitte 11.2 und 11.3
    
  • Scott Aaronson: Lecture notes! Intro to Quantum Information Science
  • Ronald de Wolf: Quantum Computing: Lecture Notes
  [Direktlink] [Youtube]

• Quantenrechner
  Quanten-Schaltkreise, Quantengatter, No-Cloning-Theorem, Bitflip-Gatter, Phasenflip-Gatter, Phasen-Gatter, Hadamard-Gatter, Controlled-U-Gatter, Toffoli-Gatter, universelle Quanten-Gatter, Zwischenmessungen, Versand von Qubits über einen klassischen Kanal (Quantenteleportation)
  Referenzen:
  • Folien: Quantenalgorithmen (38-54) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 11.4
    
  • Scott Aaronson: Lecture notes! Intro to Quantum Information Science
  • Ronald de Wolf: Quantum Computing: Lecture Notes
  [Direktlink] [Youtube]

• Quanten-Turingmaschinen
  
  Referenzen:
  • Folien: Quantenalgorithmen (55-65) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitte ...
    
  • Scott Aaronson: Lecture notes! Intro to Quantum Information Science
  • Ronald de Wolf: Quantum Computing: Lecture Notes
  [Direktlink] [Youtube]

• BQP
  
  Referenzen:
  • Folien: Quantenalgorithmen (66-77) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt ...
    
  • Scott Aaronson: Lecture notes! Intro to Quantum Information Science
  • Ronald de Wolf: Quantum Computing: Lecture Notes
  [Direktlink] [Youtube]

• Grovers Algorithmus
  das Suchproblem zu einer booleschen Funktion (finde x mit f(x)=1), die Zustände Good und Bad, der Operator U
  Referenzen:
  • Folien: Quantenalgorithmen (78-86) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 11.5.2
    
  • Scott Aaronson: Lecture notes! Intro to Quantum Information Science
  • Ronald de Wolf: Quantum Computing: Lecture Notes
  [Direktlink] [Youtube]

• Die Optimalität von Grovers Algorithmus im Orakel-Modell
  die Sprache L_A, NP^A ⊈ BQP^A, ein schwieriges Orakel A, Hybrid-Argument, ein vereinfachendes Fazit (n Grashalme, eine Stecknadel, randomisierter und Quanten-Ansatz)
  Referenzen:
  • Folien: Quantenalgorithmen (87-96) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 11.5.2
    
  • Scott Aaronson: Lecture notes! Intro to Quantum Information Science
  • Ronald de Wolf: Quantum Computing: Lecture Notes
  [Direktlink] [Youtube]

• QFT
  Einheitswurzeln, DFT, schnelle Multiplikation von Polynomen, Quanten-Fourier-Transformation (QFT),
  Referenzen:
  • Folien: Quantenalgorithmen (109-121) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 12.1
    
  • Scott Aaronson: Lecture notes! Intro to Quantum Information Science
  • Ronald de Wolf: Quantum Computing: Lecture Notes
  [Direktlink] [Youtube]

• Shor
  Periodenbestimmung führt auf schnelle Faktorisierung, Shors Algorithmus für die Periodenbestimmung, Analyse des Algorithmus
  Referenzen:
  • Folien: Quantenalgorithmen (122-135) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 12.2
    
  • Scott Aaronson: Lecture notes! Intro to Quantum Information Science
  • Ronald de Wolf: Quantum Computing: Lecture Notes
  [Direktlink] [Youtube]

• Simon
  Es gibt ein Orakel A, so dass BPP^A ⊂ BQP^A, Simons Algorithmus bestimmt das Geheimnis s einer 2-bijektiven Funktion f_n mit hoher Wahrscheinlichkeit nach O(n) Orakel-Anfragen, aber klassische randomisierte Algorithmen benötigen exponentiell viele Anfragen, Zusammenfassung
  Referenzen:
  • Folien: Quantenalgorithmen (97-108) [ Druckversion | Bildschirmversion ]
    
  • Skript: Abschnitt 11.5.3
    
  • Scott Aaronson: Lecture notes! Intro to Quantum Information Science
  • Ronald de Wolf: Quantum Computing: Lecture Notes
  [Direktlink] [Youtube]

• Hamilton
  Hamilton-Operator, Matrizen exponentieren, Evolution in kontinuierlicher Zeit, Schrödingergleichung, e^-iHt und der Hamiltonoperator H, Energieniveaus und Energieeigenzustände, gleichzeitiger Einfluss als Summe von Hamiltonoperatoren, k-lokale Hamiltonians, Max-3SAT und 3-lokale Hamiltonians, die Klasse Quantum-Merlin-Arthur (QMA)
  Referenzen:
  • Folien: Quantenalgorithmen (136-150) [ Druckversion | Bildschirmversion ]
    
  • Scott Aaronson: Lecture notes! Intro to Quantum Information Science
  • Ronald de Wolf: Quantum Computing: Lecture Notes
  [Direktlink] [Youtube]