Sind Informatik-Beweise auch mathematische Beweise?

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.

Posted by

ist promovierter Mathematiker und forscht in der Abteilung Optimierung des Konrad-Zuse-Instituts in Berlin. Dort leitet er die Arbeitsgruppe Energie, die sich vor allem mit Optimierungsproblemen für Gasnetze befasst. Zum Bloggen für das HLF kam er als Klaus-Tschira-Preisträger für verständliche Wissenschaft “KlarText!”.

2 comments Write a comment

  1. 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.

    Mal ganz wild geraten: Die Kollegen um Micali haben ebenfalls geraten und versuchen mit Hilfe statistischer Maßnahme mathematische Beweise anzutreten.

    Ausschnittsweise auf mathematische Behauptungen zugreifend und rechnend.

    MFG
    Dr. W

  2. Missverständnisse vorherbestimmt?

    In der theoretischen Informatik ist doch der Begriff des Beweises eigentlich der gleiche wie in der Mathematik.

    Wenn man jetzt ein System baut, dass mit Zufällen arbeitet, sind die Schlussfolgerungen immer nur mit einem Wahrscheinlichkeitswert behaftet. Es ist ja eigentlich auch klar, dass “wahrscheinlich wahr” eben nicht das Gleiche wie “wahr” ist. Deswegen hätte man für das Zero-Knowledge-Verfahren durchaus einen besseren Namen finden können als “Beweis”. Vielleicht einfach “Nachweis”? Denn zum Beispiel in der empirischen Forschung wird mit Messungen ja auch nichts bewiesen sondern nur Korrelationen nachgewiesen.

    Aus meiner Sicht ist das ein Missverständnis mit Ansage.

    Was das ganze dann aber auch noch mit der Komplexitätstheorie zu tun haben soll, erschließt sich mir nun gar nicht mehr. Braucht man das um die unterschiedliche Verwendung des Begriffs “Beweis” zu verstehen? Braucht man es um um Zero-Knowledge-Beweise zu verstehen? Falls ja, wieso ist das dann nicht im verlinkten Artikel über ZKP erklärt?

    PS: Jetzt am Ende habe ich gerade noch gesehen, dass man es auch Zero-Knowledge-Protokoll nennt. Das Ganze wird daurch nicht einfacher zu verstehen. 🙂

Leave a Reply


E-Mail-Benachrichtigung bei weiteren Kommentaren.
-- Auch möglich: Abo ohne Kommentar. +