Es wirkt oft viel schwieriger, ein Problem zu lösen, als einen Lösungsvorschlag als korrekt zu verifizieren. Die mathematische Formulierung dieses intuitiven Eindrucks ist das sogenannte P-NP-Problem. Sind alle Probleme, deren Lösung man effizient überprüfen kann, auch effizient lösbar, wenn man es nur richtig anstellt? Das ist die größte ungelöste Frage der theoretischenInformatik.
Der israelische Mathematiker Avi Wigderson nennt das Problem "eine der tiefgreifendsten intellektuellen Fragen, die je gestellt wurden." Seit es das erste Mal in den 1970er-Jahren formuliert wurde, hat das Problem zu einer großen Blüte der Berechenbarkeits- und Komplexitätstheorie geführt. Vor allem für Arbeiten auf diesen Gebieten haben Wigderson vom Institute for Advanced Study in Princeton und László Lovász von der Eötvös-Loránd-Universität in Budapest kürzlich den diesjährigen Abelpreis zuerkannt bekommen, eine der bedeutendsten Auszeichnungen auf dem Gebiet derMathematik.
Der Abelpreis wird jährlich von der Norwegischen Akademie der Wissenschaften verliehen, er ist mit 7,5 Millionen Norwegischen Kronen dotiert (etwa 750 000 Euro). Der diesjährige Preis würdigt nicht nur die fruchtbaren Verbindungen zwischen Mathematik und theoretischer Informatik, sondern auch die Revolution, welche die Theorie der Algorithmen in der Forschung sowie im modernen Alltag bewirkt hat. "Algorithmen und Rechenprozesse finden nicht nur in Computern oder zwischen Computersystemen statt, sondern überall: in Atomen, in Materie, bei Facebook, in den Preisen in einer Volkswirtschaft, in den Bakterien einer Zelle, in den Neuronen im Gehirn", sagte Wigderson in einem Interview. "Um diese großen wissenschaftlichen Fragen zu verstehen und Theorien für ihre Erforschung zu entwickeln, müssen wir die Vorgänge in diesen Systemenverstehen."
Wigderson, Sohn von Holocaust-Überlebenden, wurde 1956 in Israel geboren. Dort studierte er am Technion in Haifa, bevor er an der Princeton-Universität promovierte. Nach mehreren Jahren als Professor an der Hebräischen Universität in Jerusalem wurde er 1999 Professor am Institute for Advanced Study. Seither hat er dort ein internationales Zentrum für theoretische Informatikaufgebaut.
Zu Beginn seiner Karriere machte Wigderson bahnbrechende Fortschritte auf dem Gebiet des P-NP-Problems, indem er den Einfluss des Zufalls auf die Berechenbarkeit untersuchte. Zufallsbasierte Methoden entscheiden über manche Lösungsschritte quasi per Münzwurf. Manchmal können sie damit schwere Probleme knacken, die mit nicht-zufälligen Methoden nicht gelöst werden können. Der Preis dafür ist, dass solche Methoden manchmal die falsche Antwort liefern. Wigderson zeigte mit Kollegen, dass für jede Methode, die ein Problem per Münzwurf lösen kann, eine fast genauso effiziente Methode ohne Zufallselement existiert. Das Ergebnis führte zu einer Explosion von Forschungsarbeiten über den Zusammenhang zwischen Zufall und der Komplexität vonBerechnungen.
Wie kann man belegen, dass man über eine Information verfügt, ohne sie preiszugeben?
In den 1980ern entwickelten Wigderson und seine Kollegen den kontraintuitiven Begriff des kenntnisfreien Beweises. Hat man einen mathematischen Satz bewiesen, so ist der einzige Weg, jemand anderen davon zu überzeugen, der anderen Person den Beweis zu verraten. Oder? Nicht ganz. Ein kenntnisfreier Beweis ist ein Verfahren, mit dem man die andere Person überzeugen kann, ohne jegliche Informationen über den Beweis preiszugeben. Das Verfahren führt den anderen durch eine Reihe von Experimenten, die unbestreitbar belegen, dass man über den Beweis verfügt, ohne ihn vorführen zu müssen. Während kenntnisfreie Beweise zuerst als zu unpraktisch galten, um von praktischer Bedeutung zu sein, werden sie heute für die Blockchain-Technologie und Digitalwährungenverwendet.
Ein verwandtes Thema sind "probabilistisch prüfbare Beweise" (PCP), ein Gebiet, auf dem der andere Preisträger, László Lovász, wegweisende Resultate erzielte. Angenommen, jemand müsste für ein Mathematik-Journal einen 1000-seitigen Beweis für ein Satz überprüfen. Vielleicht enthält der Beweis einen Fehler - aber wie könnte man das wissen, ohne alles genau gelesen zu haben? Mit der PCP-Methode kann man den Beweis in einem Format aufschreiben, das es erlaubt nur noch einen kleinen Teil davon zu überprüfen, um mit hoher Wahrscheinlichkeit seine Korrektheit festzustellen. PCP ist inzwischen ein großes Forschungsgebiet in der theoretischen Informatikgeworden.
Ungarn hat eine lange Tradition in diskreter Mathematik, die sich mit diskreten Objekten wie den ganzen Zahlen befasst statt mit kontinuierlichen Objekten wie etwa Sinuskurven. Als der größte Vertreter dieses Bereichs der Mathematik gilt der legendäre Paul Erdös. Als Jugendlicher waren die Begegnungen mit Erdös eine große Inspiration für Lovász. "Lovász ist ein großartiger Mathematiker, der als starker ,Problemlöser' begonnen hat", sagt Günter Ziegler, Mathematiker und Präsident der Freien Universität Berlin. "Er ist jedoch nicht nur ein Problemlöser, sondern hat uns immer wieder mit unerwarteten Verbindungen zwischen scheinbar unzusammenhängenden Themen in Mathematik und Informatiküberrascht."
Lovász wurde 1948 in Budapest geboren. Er war ein Wunderkind, das 1964, 1965 und 1966 Goldmedaillen bei der Internationalen Mathematik-Olympiade gewann. Er bekam mit erst 22 Jahren seinen Doktortitel an der Eötvös-Loránd-Universität verliehen. Nach Anstellungen an der Yale University und bei Microsoft Research wurde er 2006 Professor an der-Eötvös-Loránd Universität. In den vergangenen Jahren ist er während seiner zweiten Amtszeit als Präsident der Ungarischen Akademie der Wissenschaften in einen Konflikt mit der rechtspopulistischen Regierung von Viktor Orbán geraten. Diese hatte ein Gesetz entworfen, das einen großen Teil des Forschungsbudgets in die Hände des Innovations- und Technologieministeriums legt. Lovász hat sich dagegen gewehrt, und die Freiheit der Wissenschaft verteidigt. Wissenschaftler in Ungarn und Europa protestierten mit offenen Briefen. Verhindert werden konnte die Regelung jedochnicht.
Einer von Lovászs bedeutendsten Durchbrüchen ist der LLL-Algorithmus, den er zusammen mit den niederländischen Brüdern Arjen und Hendrik Lenstra entwickelte. Bei seiner Publikation 1982 wurde der Algorithmus aufgrund seiner Einfachheit und breiten Anwendbarkeit als eine der herausragenden algorithmischen Leistungen des 20. Jahrhunderts gepriesen. Ursprünglich entwickelt, um Polynome in Faktoren zu zerlegen, wurde der LLL-Algorithmus mittlerweile in einer Vielzahl von Gebieten verwendet, einschließlich der Kryptografie. Der Algorithmus war entscheidend, um Gitter-basierte Verschlüsselungssysteme zu entwickeln, die heute als einzige den Attacken eines Quantencomputers gewachsensind.
Beide Preisträger sind sehr beliebt, freundlich und zugänglich. Lovász ist eher leise und bescheiden, Wigderson charmant und überschwänglich. Gil Kalai, Mathematiker an der Hebräischen Universität Jerusalem, kennt sie beide. "Ihre Großzügigkeit und Freundlichkeit sowie ihre Aufrichtigkeit und ihr Anstand sind Teil ihres Erfolgs", sagter.
Übersetzung: Peter Strigl
