Als Avi Wigderson und László Lovász ihre Karriere in den 1970er Jahren begannen, waren die theoretische Informatik und die reine Mathematik zwei völlig unterschiedliche Fächer. Doch heute stehen sie sich so nahe, dass es schwer ist, eine Grenze zwischen ihnen auszumachen. Die zwei Wissenschaftler erhielten für ihre grundlegenden Beiträge in beiden Gebieten – und für das Zusammenführen der Disziplinen – den diesjährigen Abelpreis. Diese Auszeichnung vergibt die Norwegischen Akademie der Wissenschaften und der Literatur und gilt als eine der höchsten Ehrungen in der Mathematik.

»In vielerlei Hinsicht ist ihre Arbeit komplementär. Avi arbeitet auf der Seite der Informatik, während Lovász Mathematiker ist. Aber viele der Themen, mit denen sie sich beschäftigen, sind verwandt«, sagt der Computerwissenschaftler Russell Impagliazzo von der University of California, San Diego.

Ein Maß für die Schwierigkeit

Wigderson wurde 1956 in Haifa, Israel, geboren. Als er ein Teenager war, begannen Informatiker gerade, ein theoretisches Gerüst zu entwickeln, das einen Großteil seines künftigen Berufslebens beeinflussen sollte. In diesem Rahmen, der Komplexitätstheorie, klassifiziert man Rechenprobleme danach, wie schwer sie für Algorithmen zu lösen sind. Als primäres Maß gilt die Anzahl der benötigten Rechenschritte. Die grundlegendste Unterscheidung ist dabei einfach versus kompliziert.

Ein Beispiel für ein simples Rechenproblem ist die Multiplikation zweier Zahlen: Egal wie groß die Werte sind, Computer können das Produkt schnell ermitteln. Die Aufgabe gehört somit zur Komplexitätsklasse P, die alle leicht zu lösenden Rechenprobleme enthält.

Im Gegensatz dazu scheint die Primfaktorzerlegung zu den schweren Problemen zu zählen, denn es gibt keinen bekannten Algorithmus, der es allgemein schnell lösen kann. Wenn man hingegen die Primfaktoren einer Zahl vorgelegt bekommt, lässt sich einfach nachrechnen, ob es sich tatsächlich um die richtigen Werte handelt, indem man sie miteinander multipliziert. Deshalb gehört die Primfaktorzerlegung zur Komplexitätsklasse NP, die neben den Rechenproblemen von P auch solche enthält, die schwer zu lösen sind, deren Antworten sich hingegen leicht überprüfen lassen.

Doch nur weil man noch keinen schnellen Algorithmus zur Lösung einer Aufgabe kennt, heißt das nicht, dass keiner existiert. Und so formulierten Informatiker in den frühen 1970er Jahren eine berühmte Frage: Entsprechen die Probleme in P denjenigen in NP? Oder anders ausgedrückt: Gibt es zu jeder leicht zu überprüfenden Aufgabe einen Algorithmus, der sie schnell löst?

Als Wigderson 1977 das Technion (das Israelische Institut für Technologie) betrat, war dieses so genannte P-NP-Problem noch jung. »Als ich mit meiner Doktorarbeit begann, entwickelte sich die Komplexitätstheorie gerade zu einem ausgereiften Feld«, erinnert er sich. In den kommenden Jahrzehnten sollte er viele grundlegende Beiträge dazu leisten – und herausarbeiten, welche Probleme unter welchen Umständen in welche Klassen fallen.

Perfektes Matching

In den späten 1980er Jahren untersuchten Wigderson und sein Mitarbeiter Ran Raz die Komplexität des »perfekten Matchings« (eine Frage, die auch in Lovász' Arbeit auftaucht): Stellen Sie sich vor, es gibt 20 Maschinen, die jeweils einige – aber nicht alle – von 20 verschiedenen Aufgaben ausführen können. Beim perfekten Matching versucht man die Maschinen so einzustellen, damit alle Aufgaben abgedeckt sind und jedes Gerät genau eine ausführt.

Wigderson und Raz untersuchten das Problem, indem sie nach einem passenden Algorithmus suchten, um die Aufgabe zu lösen. Allerdings schränkten sie dafür die Fähigkeiten des Computers, der sie bearbeiten sollte, ein: Sie stellten sich vor, der Rechner könne die meisten Standard-Logikoperationen (wie »und« und »oder«) ausführen, aber eine entscheidende nicht: die Nicht-Operation.

Natürlich würden Informatiker am liebsten ohne solche Annahmen beweisen, dass eine Rechenaufgabe kompliziert ist, aber das ist ihnen bisher nicht gelungen. »Man will die Grenzen von Algorithmen finden, und wenn man das nicht in der allgemeinsten Einstellung tun kann, schränkt man sie eben ein«, so Wigderson. Deshalb versuchen Computerwissenschaftler zu zeigen, dass es keinen schnellen Algorithmus für ein Problem wie das perfekte Matching gibt, wenn man sowohl die Rechenressourcen als auch die zur Verfügung stehende Zeit begrenzt. So konnten Wigderson und Raz 1990 beweisen, dass sich das Matching-Problem auf Computern ohne die Nicht-Operation nicht effizient lösen lässt.

Alles nur Zufall?

Etwa zur gleichen Zeit arbeitete Wigderson an einer zentralen Frage der Komplexität: Beeinflusst der Zufall die Geschwindigkeit, um ein Rechenproblem zu lösen? Seit den 1970er Jahren vermuteten Informatiker, dass Elemente des Zufalls den Berechnungsprozess beschleunigen. Trifft ein Algorithmus während seines Entscheidungsprozesses zufällige Entscheidungen – etwa beim Testen, ob eine Zahl eine Primzahl ist – gelangt er manchmal schneller zu einer Lösung, als wenn er jeden Schritt deterministisch wählt.

Wigderson und seine Kollegen konnten in den 1990er Jahren aber in zwei Arbeiten zeigen, dass es unter bestimmten Annahmen immer möglich ist, einen schnellen Zufallsalgorithmus in einen effizienten deterministischen Algorithmus umzuwandeln. Wie sie bewiesen, entspricht die Komplexitätsklasse BPP (die Probleme enthält, die sich schnell durch Zufallsalgorithmen lösen lassen) unter diesen Annahmen der Klasse P. Das veränderte die Art und Weise, wie Informatiker zufällige Algorithmen betrachteten. »Heute wird wohl fast jeder sagen, dass der Zufall eine schwache Methode ist. Denn er lässt sich beseitigen – zwar nur unter bestimmten Annahmen, aber wir sind fest davon überzeugt, dass sie richtig sind«, so Wigderson.

Der Informatiker, der seit 1999 am Institute for Advanced Study tätig ist, hat zahlreiche weitere Ergebnisse in dem Gebiet hervorgebracht, darunter das so genannte Zickzackprodukt, das mit mehreren mathematischen Bereichen zusammenhängt: Es bietet eine Strategie, um aus einem Labyrinth zu entkommen, wobei man nur eine bestimmte Anzahl von Kreuzungen berücksichtigt. Die Vielfältigkeit von Wigdersons Arbeiten verdeutlicht, wie sich die Komplexitätstheorie seit seinem Eintritt in den Forschungsbereich erweitert hat.

Mathematisches Wunderkind

Während Wigderson die Grenzen der Komplexitätstheorie immer weiter verschob, war Lovász in einem eng verwandten Gebiet tätig, das ebenfalls noch viel Raum zum Wachsen hatte. Der 1948 in Budapest geborene Lovász war schon in jungen Jahren ein Star der Mathematik: Als Teenager gewann er drei Goldmedaillen bei der Internationalen Mathematik-Olympiade und triumphierte in einer ungarischen Spielshow, in der Kinder in gläsernen Kabinen Probleme lösen mussten.

Früh lernte Lovász den einflussreichen Mathematiker Paul Erdős kennen, der ihn in das Gebiet der Graphentheorie einführte. Damals war der Bereich statt für handfeste Wissenschaft eher für unterhaltsame Probleme wie die Vier-Farben-Vermutung (heute ein bewiesener Satz) bekannt. Diese dreht sich um die Frage, ob es immer möglich ist, die Länder in einer beliebigen Karte mit nur vier Farben zu kolorieren, wobei keine zwei angrenzenden Gebiete gleichfarbig sein dürfen. »Zu dieser Zeit zählte die Graphentheorie nicht zur Mainstream-Forschung, weil viele der Probleme oder Ergebnisse aus Rätseln oder einer Art Unterhaltung entstanden«, so Lovász, der jetzt an der Eötvös-Loránd- Universität in Ungarn arbeitet. Aber die Dinge änderten sich, als er 1970 im Alter von 22 Jahren seinen Doktortitel erwarb. Hauptgrund dafür waren die Entwicklungen in der Computerwissenschaft.

Computer arbeiten zwangsläufig mit diskreten Größen – binären Zeichenfolgen aus Einsen und Nullen. Die Kombinatorik ist die Mathematik diskreter Objekte, und eines ihrer wichtigsten Teilgebiete ist die Graphentheorie, die Netzwerke von Kanten untersucht, die Punkte miteinander verbinden. Als solche bot sie eine Art Sprache, um an Problemen der theoretischen Informatik zu arbeiten. Lovász betrachtet den gemeinsamen Aufstieg der Computerwissenschaften und der Graphentheorie als ein günstiges historisches Zusammentreffen. Er vergleicht den Prozess mit der modernen Entwicklung der Analysis, die mehr als ein Jahrhundert zuvor durch physikalische Fragen vorangetrieben wurde.

Lovász entwickelte zahlreiche Algorithmen, um verschiedenste Probleme zu lösen. Eines seiner einflussreichsten Ergebnisse ist der LLL-Algorithmus, benannt nach seinen Schöpfern, Lovász und den Brüdern Arjen und Hendrik Lenstra. Er befasst sich mit einer grundlegenden Frage, welcher Punkt eines Gitters dem Ursprung am nächsten ist? Das mag einfach klingen, doch in hoch dimensionalen Räumen mit verzerrten Gitterformen lässt sich die Aufgabe nur schwer lösen. Anstatt das Problem exakt zu beantworten, liefert der LLL-Algorithmus eine gute Näherung: Er identifiziert eine Lösung mit der Zusicherung, dass es keinen anderen Punkt gibt, der viel näher am Ursprung liegt. Weil das Gittermodell so allgemein ist, findet der Algorithmus in zahlreichen Gebieten Anwendung, von der Faktorisierung von Polynomen bis hin zum Testen der Sicherheit kryptografischer Systeme.

Probabilistische Graphen

Ein weiterer bedeutender Beitrag von Lovász betrifft den Bereich der Wahrscheinlichkeitsrechnung. In den 1960er Jahren entwickelte Paul Erdős eine probabilistische Methode, um Fragen über Graphen anzugehen. Häufig möchten Mathematiker wissen, ob ein Netzwerk mit bestimmten Eigenschaften existiert. Dafür kann man entweder ein Beispiel finden, das die geforderten Merkmale besitzt. Aber Erdős arbeitete einen anderen Ansatz aus, indem man beweist, dass ein zufällig ausgewählter Graph die gewünschten Eigenschaften mit hoher Wahrscheinlichkeit innehat.

Allerdings funktionierte die Methode am besten für Netzwerke, die man bereits kannte. In den 1970er Jahren erweiterte Lovász zusammen mit Erdős daher das Verfahren, indem sie das so genannte Lovász-Lokal-Lemma erarbeiteten. Damit konnten sie die Existenz von Graphen beweisen, die extrem selten sind. Dieser Beitrag hat sich zu einer der wichtigsten Techniken auf diesem Gebiet entwickelt.

In seiner Karriere hat Lovász viele andere Probleme der Graphentheorie gelöst, darunter die Vermutung von Kneser über die kleinste Anzahl von Farben, die man zum Kolorieren eines bestimmten Graphen benötigt. Außerdem stellte er mehrere eigene Hypothesen auf, die noch heute das Gebiet maßgeblich beeinflussen.

Zu der Zeit, als theoretische Informatiker wie Wigderson unser Verständnis von Komplexität verfeinerten, untersuchte Lovász Graphen, die dabei halfen, die Grenzen zwischen einer Komplexitätsklasse und einer anderen zu definieren. Und so ist es passend, dass die zwei Pioniere, die ihre jeweiligen Disziplinen zusammengebracht haben, nun auch durch den Abelpreis verbunden sind.