Beweise färben - Überzeugen, ohne etwas zu verraten

Kann man jemanden davon überzeugen, dass man die Riemannsche Vermutung bewiesen hat, ohne den Beweis vorzulegen? Das geht (zumindest theoretisch) mit einem sogenannten "Zero Knowledge Proof". Dieses Konzept aus der Kryptographie wird hier anhand eines schönen Beispiels von Avi Wigderson erläutert. (Wigderson bekam kurz nach Veröffentlichung dieses Videos den Abelpreis verliehen.) Eine zentrale Rolle spielt dabei der Satz von Cook und Levin aus der Komplexitätstheorie. Außerdem kommen auch Färbungen von Landkarten, Graphentheorie und das Erfüllbarkeitsproblem der Aussagenlogik (SAT) vor.
* Das GANZ NEUE Buch: weitz.de/GDM
* Das NEUE Buch: weitz.de/PP/
* KORREKTUR: weitz.de/corr/hkbgAy3WfVs
* Der Vier-Farben-Satz: • Der Vier-Farben-Satz (...
* Beweisverifikation durch Computer: • Die Keplersche Vermutu...
* Was sind Turingmaschinen? • Die seltsamste Zahl: C...
* Turingmaschinen und Nichtdeterminismus: • Theoretische Informati...
* Aussagenlogik: • Aussagen
* Graphentheore: • Warum Graphentheorie?
* NP-Vollständigkeit und der Satz von Cook und Levin: • NP-Vollständigkeit und...
* Das etwas andere Mathe-Lehrbuch: weitz.de/KMFI/
* Liste aller Videos: weitz.de/haw-videos/
* Illustrationen von Heike Stephan: / haiartandillustration
* Allgemeine Anmerkungen: weitz.de/youtube.html
00:00 Worum es geht
04:11 Färben von Landkarten und Zero Knowledge
09:32 I. Formalisierung
11:36 II. Ein nichtdeterministischer Algorithmus
16:41 III. Eine Turingmaschine
20:03 IV. Der Satz von Cook und Levin
28:22 V. Zeitin-Transformation
35:17 VI. Formeln werden zu Graphen
43:43 VII. Planare Graphen
49:03 Zusammenfassung
Corrections:
17:24 Bitte beachten Sie die Korrekturhinweise in der Videobeschreibung.