Die Laureaten

Copyright © Klaus Tschira Stiftung / Peter Badge

Madhu Sudan

geboren am 12. September 1966 in Chennai (Indien)

Nevanlinna-Preis (2002) „für herausragende Beiträge für mathematische Aspekte der Informationswissenschaften.“

Madhu Sudan studierte Informatik am Indian Institute of Technology in New Delhi (Bachelor of Technology 1987) und promovierte anschließend an der University of California, Berkeley (Ph.D. 1992). Seine Doktorarbeit schrieb er über „Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems“ bei Umesh Virkumar Vazirani. Schon als Doktorand hatte er am IBM Almaden Research Center geforscht (Sommer 1990); nach seiner Promotion arbeitete er am IBM Thomas J. Watson Research Center (1992-97). Sudan wurde dann außerordentlicher Professor am Massachusetts Institute of Technology (1997-2002) und erhielt 2003 eine Professur am MIT. Er war Fujitsu Chair Professor und Danny Lewin Outstanding Professor am MIT zwischen 2005 und 2009. Er arbeitete auch als stellvertretender Direktor des Computer Science and Artificial Intelligence Laboratory zwischen 2007 und 2009. Momentan ist Sudan ein Principal Researcher bei Microsoft Research New England und Adjunct Professor für Informatik am MIT.

Madhu Sudan erhielt zahlreiche Preise und Auszeichnungen, darunter den Gödel Prize (2001) und ein Guggenheim Fellowship (2005-06).

Besonders auf drei Gebieten hat Sudan wichtige Leistungen erbracht: Probabilistisch prüfbare Beweise, die Nicht-Approximierbarkeit von Lösungen für kombinatorische Probleme sowie fehlerkorrigierende Codes. Die Theorie der probabilistisch prüfbaren Beweise verallgemeinert die inzwischen schon klassischen Komplexitätsklassen für Probleme und ermöglicht einen ganz neuen Blick auf die Frage: Wie komplex ist ein Problem? Klassisch untersucht man, wie eine Turing-Maschine, also das theoretische Modell eines Computers, das der britische Mathematiker Alan Turing 1936 entwickelt hat, ein Problem löst bzw. einen Beweis auf Korrektheit überprüft. Bei der probabilistischen Beweisprüfung wird dieses Konzept verallgemeinert: Ein „Verifizierer“ arbeitet mit einem allmächtigen „Beweiser“ zusammen. Der Beweiser – im Prinzip eine sehr leistungsfähige Turing-Maschine – hat die Aufgabe, den Verifizierer von der Korrektheit eines Beweises zu überzeugen. Dazu stellt ihm der Verifizierer über eine gewisse Anzahl von Runden immer wieder Fragen, die der Verifizierer unter anderem mit Hilfe des Zufalls generieren kann. Man kann zeigen, dass die Klasse der Probleme, die sich mit diesem Verfahren beweisen lassen, größer ist als die der „harten“ Probleme der Computerwissenschaft und Mathematik, die NP genannt wird. Tatsächlich bewies Sudan zusammen mit Kollegen, dass die Klasse NP genau solche Probleme enthält, bei denen der Verifizierer nur einen kleinen Teil (das heißt: eine konstante Anzahl von Bits) des Beweises überprüfen muss, den ihm in jeder Runde der Beweiser überreicht, und das über eine relativ kleine Anzahl von Runden.

Dieser Beweis war für die Fachwelt überraschend, zumal er noch weitere erstaunliche Implikationen hat. Unter gewissen Annahmen kann man mit ihm nämlich zeigen, dass es Probleme gibt, die sich nicht einmal näherungsweise durch schnelle Algorithmen lösen (also approximieren) lassen; sie sind also in einem gewissen Sinne wirklich „hart“. Das ist deshalb interessant, weil es eine der Kernfragen der Computerwissenschaft berührt, die Frage „Ist P=NP?“, in der es darum geht, ob es für jedes Problem in NP einen schnellen Algorithmus gibt.