Logbuch „Komplexitätstheorie“ (SoSe20)

Hier finden Sie Informationen zum Inhalt der jeweiligen Videos sowie ergänzende inhaltliche Bemerkungen.

Alle Videos finden Sie auch in unserer Youtube-Playlist.
Woche 1: Mo, 20.04.2020

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

Woche 2: Mo, 27.04.2020

  • 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: [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]

Woche 3: Mo, 04.05.2020

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: [Direktlink] [Youtube]

  • Platz und Laufzeit
    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: [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]

Woche 4: Mo, 11.05.2020

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: [Direktlink] [Youtube]

  • Randomisierte Reduktionen
    Promise-Probleme: Unique-SAT, Isolationsmethode, Zusammenfassung

    Referenzen: [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: [Direktlink] [Youtube]

Woche 5: Mo, 18.05.2020

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: [Direktlink] [Youtube]

  • Pseudo-Random-Funktionen
    Pseudo-Random-Funktionen aus PRGs, kollisionsresistente Hashfunktionen, Nachrichten-Authentifizierung mit privatem Schlüssel

    Referenzen: [Direktlink] [Youtube]

  • 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: [Direktlink] [Youtube]

Woche 6: Mo, 25.05.2020

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: [Direktlink] [Youtube]

  • Einführung in die Gitter-Kryptographie
    Gitter, Parallelotop/Grundmasche, Eigenschaften von Gittern, Shortest-Vektor-Probleme (SVP, SVPγ, Gap-SVPγ, SIVPγ, CVP)

    Referenzen: [Direktlink] [Youtube]

  • 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: [Direktlink] [Youtube]

Woche 7: Mo, 01.06.2020

Woche 8: Mo, 08.06.2020

Woche 9: Mo, 15.06.2020

Woche 10: Mo, 22.06.2020

Woche 11: Mo, 29.06.2020

Woche 12: Mo, 06.07.2020

Woche 13: Mo, 13.07.2020