Logbuch „Komplexitätstheorie“ (SoSe20)
Hier finden Sie Informationen zum Inhalt der jeweiligen Videos sowie ergänzende inhaltliche Bemerkungen.
- Woche 1 (Einführung, Laufzeit, Worst-Case-Laufzeit, Diagonalisierung und Orakel)
- Woche 2 (Einführung in die Speicherplatzkomplexität, DL und NL, Chomsky-Hierarchie, Satz von Savitch, Satz von Immerman und Szelepcsenyi)
- Woche 3 (PSPACE, Einführung in die Parallelität, Platz und Laufzeit, P-Vollständigkeit)
- Woche 4 (BPP, Randomisierte Reduktionen, One-Way-Funktionen)
- Woche 5 (Pseudo-Random-Generatoren, Pseudo-Random-Funktionen, Natürliche Beweise)
- Woche 6 (Trapdoor-Funktionen, Einführung in die Gitter-Kryptographie, Short Integer Solution)
- Woche 7 (Beweis des SIS-Hauptsatzes, Learning with Errors I)
- Woche 8 (Learning with Errors II, Hilberträume, Operatoren und Messungen I)
- Woche 9 (Operatoren und Messungen II, Quantenrechner)
- Woche 10 (Quanten-Turingmaschinen, BQP)
- Woche 11 (Grovers Algorithmus, Optimalität)
- Woche 12 (QFT, Shor)
- Woche 13 (Simon, Hamilton)
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.
- Folien: Einführung (1-8)
[ Druckversion |
Bildschirmversion ]
- 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
- 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
- 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
- Einführung in die Speicherplatzkomplexität
Speicherplatzklassen (deterministisch, nichtdeterministisch, alternierend), sublogarithmischer und logarithmischer Speicherplatz Referenzen:- Folien: Speicherplatz (1-17)
[ Druckversion |
Bildschirmversion ]
- Folien: Speicherplatz (1-17)
[ Druckversion |
Bildschirmversion ]
- Kapitel 8 in M. Sipser, Introduction to the Theory of Computation, Paperback 3rd edition, Cengage Learning, 2012.
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.
von Grammatiken erzeugte Sprachen: reguläre, kontextfreie, kontextsensitive und rekursiv-aufzählbare Sprachen Referenzen:
- Folien: Speicherplatz (31-42)
[ Druckversion |
Bildschirmversion ]
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.
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.
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 ]
- Folien: Speicherplatz (57-72)
[ Druckversion |
Bildschirmversion ]
- Kapitel 8 in M. Sipser, Introduction to the Theory of Computation, Paperback 3rd edition, Cengage Learning, 2012.
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
Zusammenhang zwischen Speicherplatz und Tiefe von Schaltkreisen (NC1 ⊆ DL ⊆ NL ⊆ NC2, DEPTHuniform(s) ⊆ DSPACE(s) ⊆ NSPACE(s) ⊆ DEPTHuniform(s2), D-REACHABILITY liegt vermutlich nicht in NC1) Referenzen:
- Folien: Speicherplatz (15-20)
[ Druckversion |
Bildschirmversion ]
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.
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 ⊆ Σp2 ∩ Πp2 Referenzen:- Folien: Randomisierte Algorithmen (1-17)
[ Druckversion |
Bildschirmversion ]
- Folien: Randomisierte Algorithmen (1-17)
[ Druckversion |
Bildschirmversion ]
Promise-Probleme: Unique-SAT, Isolationsmethode, Zusammenfassung Referenzen:
- Folien: Randomisierte Algorithmen (18-23)
[ Druckversion |
Bildschirmversion ]
-
Skript: Abschnitt 7.2
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
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
- Folien: Kryptographie (12-32)
[ Druckversion |
Bildschirmversion ]
- 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
- Folien: Kryptographie (33-46)
[ Druckversion |
Bildschirmversion ]
- Natürliche Beweise
Wieso ist der Nachweis von P ≠ NP so schwierig? Größe und Tiefe von Schaltkreisen, Empfindlichkeit, natürliche Eigenschaften, AC0, boolesche PRFs haben keine Schaltkreise polynomieller Größe Referenzen:- Folien: Natürliche Beweise (1-14)
[ Druckversion |
Bildschirmversion ]
-
Skript: Abschnitt 8.1.2.1
- Folien: Natürliche Beweise (1-14)
[ Druckversion |
Bildschirmversion ]
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
- Folien: Kryptographie (47-61)
[ Druckversion |
Bildschirmversion ]
- 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
- Folien: Kryptographie (62-68)
[ Druckversion |
Bildschirmversion ]
- Short Integer Solution
SISn,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
- Folien: Kryptographie (69-75)
[ Druckversion |
Bildschirmversion ]
- Beweis des SIS-Hauptsatzes
Referenzen:- Folien: Kryptographie (76-84)
[ Druckversion |
Bildschirmversion ]
-
Skript: Abschnitt 8.3.1.1
- Chris Peikert: A Decade of Lattice Cryptography
- Folien: Kryptographie (76-84)
[ Druckversion |
Bildschirmversion ]
- 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
- Folien: Kryptographie (85-102)
[ Druckversion |
Bildschirmversion ]
- 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
- Folien: Kryptographie (103-111)
[ Druckversion |
Bildschirmversion ]
- 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
- Folien: Quantenalgorithmen (1-16)
[ Druckversion |
Bildschirmversion ]
- 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
- Folien: Quantenalgorithmen (17-24)
[ Druckversion |
Bildschirmversion ]
- 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
- Folien: Quantenalgorithmen (25-37)
[ Druckversion |
Bildschirmversion ]
- 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
- Folien: Quantenalgorithmen (38-54)
[ Druckversion |
Bildschirmversion ]
- 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
- Folien: Quantenalgorithmen (55-65)
[ Druckversion |
Bildschirmversion ]
- 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
- Folien: Quantenalgorithmen (66-77)
[ Druckversion |
Bildschirmversion ]
- 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
- Folien: Quantenalgorithmen (78-86)
[ Druckversion |
Bildschirmversion ]
- Die Optimalität von Grovers Algorithmus im Orakel-Modell
die Sprache LA, NPA ⊈ BQPA, 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
- Folien: Quantenalgorithmen (87-96)
[ Druckversion |
Bildschirmversion ]
- 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
- Folien: Quantenalgorithmen (109-121)
[ Druckversion |
Bildschirmversion ]
- 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
- Folien: Quantenalgorithmen (122-135)
[ Druckversion |
Bildschirmversion ]
- Simon
Es gibt ein Orakel A, so dass BPPA ⊂ BQPA, Simons Algorithmus bestimmt das Geheimnis s einer 2-bijektiven Funktion fn 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
- Folien: Quantenalgorithmen (97-108)
[ Druckversion |
Bildschirmversion ]
- 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
- Folien: Quantenalgorithmen (136-150)
[ Druckversion |
Bildschirmversion ]