Am Dienstag hielt Silvio Micali, einer der Erfinder der bereits skizzierten Zero-Knowledge-Beweissysteme, einen für mich sehr gut zu verstehenden, enthusiastischen Vortrag. Allerdings habe ich bei einigen Gesprächen danach festgestellt, dass derselbe Vortrag für die mathematischen Kollegen gleich zu Beginn sehr irritierend war. Scheinbar hat die Informatik (zumindest die von Micali vertretene) ein sehr fragwürdiges Konzept von einem Beweis. Da Beweise bekanntlich der Heilige Gral der Mathematik sind, sind Mathematiker hier sehr empfindlich. Es ist für sie bereits besorgniserregend, dass die von Micali skizzierten interaktiven Beweise eine zufällige Komponente enthalten. Als wirklich schlimm empfinden sie allerdings, dass es mit einer (beliebig kleinen) Wahrscheinlichkeit möglich ist, dass ein Beweis geglaubt wird, obwohl er falsch ist.

Nachdem ich dieses Wahrnehmungsproblem verstanden hatte, habe ich mehr oder weniger erfolgreich versucht, die Motivation von interaktiven Beweisen zu erklären. Entstanden sind diese in der Komplexitätstheorie, in der theoretische Informatiker versuchen, den zur Lösung von Problemen benötigten Rechenaufwand zu bestimmen. Mathematische Beweise können im Prinzip sehr lang sein, vielleicht zu lang zum Lesen und Prüfen. Welche Beweise kann man effizient, also in kurzer Zeit prüfen? Effizient wird meist mit sogenannter polynomieller Zeit gleichgesetzt. Das heißt, die benötigte Rechenzeit wächst höchstens als Polynom der Problemgröße, wird also nicht zu schnell sehr groß. Wenn ein Beweis zu lang ist, sagen die Informatiker, können wir in kurzer Zeit eben nur Teile des Beweis anschauen und prüfen. Die geprüften Teile müssen zufällig gewählt werden, da sonst vielleicht immer die Teile eines falschen Beweises angeschaut werden, die richtig sind. Im Ergebnis werden also potenzielle Beweise durch einen probabilistischen Algorithmus, der Zufallsentscheidungen nutzt, geprüft.

Vorsicht, ab hier wird es sehr fachlich.

IP ist nun die Klasse von Problemen, die von einem probabilistischen Algorithmus in polynomieller Zeit überprüft werden können. Es ist bereits bekannt, dass die Klasse IP dasselbe ist, wie die Klasse PSPACE der Probleme, für die der benötigte Speicherplatz höchstens polynomiell mit der Problemgröße wächst. PSPACE enthält aber auch die Prädikatenlogik zweiter Stufe, mit der man sehr viele mathematische Aussagen formulieren kann. Jeder Satz in diesem Formalismus kann also mit polynomiell beschränktem Platz bewiesen oder widerlegt werden. Die Tatsache, dass PSPACE=IP gilt, bedeutet nun zum Beispiel, dass ein Satz der Prädikatenlogik zweiter Stufe auch in polynomieller Zeit geprüft werden kann, wenn man einen kleinen Fehler zulässt. Dies ist eines von vielen Beispielen, bei denen die Nutzung des Zufalls hilft, den Ressourcenbedarf von Algorithmen zu reduzieren, wenn man gewisse Fehlerwahrscheinlichkeiten akzeptiert.

Mir ist noch nicht restlos klar: Wie genau diese Formalisierung, bei der die Beweislänge von der Problemgröße abhängt, zu mathematischen Beweisen passt, in denen auf natürliche Weise gar keine Problemgröße vorkommt? Für die Mathematiker-Kollegen war es jedenfalls sehr beruhigend zu hören, dass diese zufallsbehafteten Beweise nicht dafür gedacht sind, herkömmliche mathematische Beweise zu ersetzen.

Diese Diskussionen und Verständnisprobleme haben mich zu der für mich überraschenden Erkenntnis gebracht, dass das HLF nicht nur Preisträger und Nachwuchs zusammenbringt, sondern auch (reine) Mathematiker und (theoretische) Informatiker. Ich denke, dass sich diese Communities sonst bei kaum einer Konferenz treffen, obwohl gerade die theoretische Informatik methodisch sehr ähnlich zur Mathematik arbeitet und auch (rein) mathematische Ergebnisse etwa der Zahlentheorie nutzt. Hier gibt es also eine weitere Ebene, auf der das HLF als Mittler wirken kann.