Avi Wigderson, Pionier der Komplexitätstheorie, gewinnt Turing Award | Quanta-Magazin

Avi Wigderson beschäftigt sich seit mehr als 40 Jahren mit Problemen. Aber als Theoretiker der rechnerischen Komplexität sind ihm die Antworten auf diese Probleme nicht unbedingt wichtig. Er möchte oft nur wissen, ob sie lösbar sind oder nicht und wie man das erkennt. „Die Situation ist lächerlich“, sagte er Wigderson, Informatiker am Institute for Advanced Study in Princeton, New Jersey. Egal wie schwierig eine Frage auch sein mag, eine effiziente Möglichkeit, sie zu beantworten, könnte darin bestehen, sich einfach außerhalb der Reichweite zu verstecken. „Soweit wir wissen, können wir für jedes Problem, mit dem wir konfrontiert sind und das wir zu lösen versuchen, nicht ausschließen, dass es einen Algorithmus hat, der es lösen kann. Das ist für mich das interessanteste Problem.“

Heute wurde Wigderson zum Sieger gekürt AM Turing-Preis, der weithin als eine der höchsten Auszeichnungen in der Informatik gilt, für seine grundlegenden Beiträge zur Berechnungstheorie. Wigdersons Arbeit hat nahezu jeden Bereich des Fachgebiets berührt. Seine Kollegen, Mitarbeiter und Mentees sagen, dass er immer wieder unerwartete Brücken zwischen unterschiedlichen Bereichen findet. Und seine Arbeiten zu Zufälligkeit und Berechnungen, die in den 1990er Jahren begannen, offenbarten tiefe Verbindungen zwischen Mathematik und Informatik, die den heutigen Untersuchungen zugrunde liegen.

Madhu Sudan, ein Informatiker an der Harvard University, der 2002 den Rolf-Nevanlinna-Preis (heute Abacus-Preis) gewann, sagte, Wigdersons Einfluss auf diesem Gebiet sei nicht zu übersehen. „Es ist sehr schwer, in irgendeinem Bereich der Informatik zu arbeiten, ohne sich tatsächlich mit Avis Arbeit zu überschneiden“, sagte Sudan. „Und überall findet man sehr tiefe Einsichten.“ In den späten 1980er Jahren arbeitete Sudan beispielsweise mit Wigderson an einer Arbeit, in der Zusammenhänge zwischen bestimmten mathematischen Funktionen und Polynomen untersucht wurden. Diese Arbeit war der Startschuss für Sudans gesamte Karriere. „Das ist typisch für Avi“, sagte Sudan. „Er betritt einen Raum, stellt die richtigen Fragen und geht dann weiter.“

Wigderson wuchs in Haifa, Israel, als einer von drei Söhnen einer Krankenschwester und eines Elektrotechnikers auf, beide Überlebende des Holocaust. Sein Vater liebte Rätsel und interessierte sich intensiv für grundlegende Ideen der Mathematik, die er mit seinen Kindern teilte. „Er ist der Typ, von dem ich mit diesem Virus infiziert wurde“, sagte Wigderson. Als er in den 1970er Jahren mit dem Studium am Technion in Haifa begann, wollte er Mathematik als Hauptfach studieren, aber seine Eltern rieten ihm stattdessen, Informatik zu studieren. „Sie dachten, es sei vielleicht eine gute Idee, dass ich einen Job habe, wenn ich fertig bin“, sagte er.

Er fand ein Feld voller tiefer, unbeantworteter Fragen, die im Kern mathematisch waren. Eine seiner frühesten bahnbrechenden Bemühungen konzentrierte sich auf einen scheinbaren Widerspruch: ob es möglich sei, jemand anderen davon zu überzeugen, dass eine mathematische Aussage bewiesen wurde, ohne zu zeigen, wie.

„Die Person, die den Beweis sieht, erfährt nichts über den Beweis selbst“, sagte er Ran Raz, Informatiker an der Princeton University. 1985 stellten Shafi Goldwasser, Silvio Micali und Charles Rackoff dieses Konzept vor Wissensfreie, interaktive Beweise, was seine Verwendung für einige Anweisungen demonstriert. Später erläuterte Wigderson zusammen mit Micali und Oded Goldreich diese Idee und legte die Bedingungen dar, die zeigen, dass eine Aussage bewiesen werden kann, wenn sie bewiesen werden kann hat auch einen wissensfreien Beweis.

„Dies ist ein wichtiges Ergebnis in der Kryptographie; Es ist extrem zentral“, sagte Raz. Mit einem Zero-Knowledge-Proof kann jemand nachweisen, dass er eine Nachricht mit seinem geheimen Schlüssel korrekt verschlüsselt oder signiert hat, ohne irgendwelche Informationen darüber preiszugeben. „Avi hat einige äußerst wichtige Ergebnisse in der Kryptographie erzielt, und dies ist möglicherweise das wichtigste davon.“

Aber vielleicht liegt Wigdersons grundlegendstes Ergebnis in einem anderen Bereich: der Verknüpfung der Rechenhärte mit Zufälligkeit. In den späten 1970er Jahren hatten Informatiker erkannt, dass bei vielen schwierigen Problemen Algorithmen, die Zufälligkeit verwenden, auch als probabilistische Algorithmen bezeichnet, ihre deterministischen Alternativen bei weitem übertreffen könnten. In einem 1977 BeweisBeispielsweise führten Robert Solovay und Volker Strassen einen randomisierten Algorithmus ein, der schneller bestimmen konnte, ob eine Zahl eine Primzahl ist, als die besten deterministischen Algorithmen seiner Zeit.

Bei einigen Problemen können probabilistische Algorithmen auf deterministische verweisen. In den frühen 1980er Jahren arbeitete Wigderson mit Richard Karp von der University of California in Berkeley zusammen, um die Idee der Zufälligkeit mit Problemen zu verbinden, die als rechentechnisch schwierig gelten, was bedeutet, dass kein bekannter deterministischer Algorithmus sie in angemessener Zeit lösen kann. „Wir wissen nicht, wie wir beweisen können, dass sie hart sind“, sagte Wigderson. Er und Karp fanden jedoch einen randomisierten Algorithmus für ein bestimmtes schwieriges Problem, das sie später derandomisieren konnten, und entdeckten damit effektiv einen deterministischen Algorithmus dafür. Etwa zur gleichen Zeit zeigten andere Forscher, wie Annahmen zur Rechenhärte bei Kryptographieproblemen eine Derandomisierung im Allgemeinen ermöglichen könnten.

Die unangemessene Wirksamkeit des Zufalls veranlasste ihn, über die Natur des Zufalls selbst nachzudenken. Wie andere Forscher seiner Zeit stellte er die Frage, wie notwendig es für eine effiziente Problemlösung sei und unter welchen Bedingungen es überhaupt beseitigt werden könne. „Anfangs war nicht klar, ob das nur unsere eigene Dummheit war, dass wir den Zufall nicht beseitigen können“, sagte er. „Aber die größere Frage war, ob Zufälligkeiten immer effizient beseitigt werden können oder nicht.“ Er erkannte, dass die Notwendigkeit der Zufälligkeit eng mit der Rechenschwierigkeit des Problems verknüpft war.

Für einen 1994 Papier, er und der Informatiker Noam Nisan beleuchteten diesen Zusammenhang. Sie bewiesen, dass, wenn es natürliche schwere Probleme gibt, wie die meisten Informatiker vermuten, jeder effiziente randomisierte Algorithmus durch einen effizienten deterministischen ersetzt werden kann. „Man kann den Zufall jederzeit beseitigen“, sagte Wigderson.

Wichtig ist, dass sie herausfanden, dass deterministische Algorithmen „pseudozufällige“ Sequenzen verwenden können – Datenfolgen, die zufällig erscheinen, es aber nicht sind. Sie zeigten auch, wie beliebige schwierige Probleme zum Aufbau eines Pseudozufallsgenerators genutzt werden können. Das Einspeisen der Pseudozufallsbits (anstelle der Zufallsbits) in einen probabilistischen Algorithmus führt zu einem effizienten deterministischen Algorithmus für dasselbe Problem.

Sudan sagte, dass das Papier Informatikern dabei geholfen habe, Zufälligkeitsgrade zu erkennen, die dazu beitragen könnten, die Feinheiten schwieriger Probleme aufzudecken und zu lösen. „Es geht nicht nur um Zufälligkeit, sondern um die Wahrnehmung von Zufälligkeit“, sagte er. „Das ist der Schlüssel.“

Sudan weist darauf hin, dass Zufälligkeit scheinbar überall auftauche, in Wahrheit aber äußerst schwer zu finden sei. „Die Leute sagen einem, dass die Ziffern von Pi zufällig aussehen oder dass die Folge von Primzahlen zufällig aussieht“, sagte er. „Sie sind völlig determiniert, erscheinen uns aber zufällig.“ Die Wahrnehmung von Zufälligkeit sei das Herzstück der heutigen Informatik, sagte er. „Und das ist etwas, das Avi enorm gefördert hat.“

Zufälligkeit ist zu einer mächtigen Ressource in der Komplexitätstheorie geworden, aber sie ist schwer zu fassen. Münzwürfe und Würfelwürfe, betont Wigderson, sind nicht wirklich zufällig: Wenn man über genügend Informationen über das physikalische System verfügt, ist das Ergebnis völlig vorhersehbar. Perfekte Zufälligkeit, sagte er, sei schwer zu fassen und schwer zu überprüfen.

Aber für Wigerson gibt es überall Beispiele für Computer – nicht nur in Smartphones und Laptops und Verschlüsselungsalgorithmen, sondern auch in biologischen und physikalischen Systemen. In den letzten Jahrzehnten haben Erkenntnisse aus der Computertheorie Einblicke in eine Reihe unerwarteter Probleme gebracht, von Vogelschwärmen und Wahlergebnissen bis hin zu biochemischen Reaktionen im Körper. „Grundsätzlich ist jeder natürliche Prozess eine Entwicklung, die man als Berechnung betrachten und als solche studieren kann. Fast alles berechnet sich.“