|
Steven RudichSteven Rudich (* 4. Oktober 1961; † 29. Oktober 2024[1]) war ein US-amerikanischer Informatiker, der sich mit Komplexitätstheorie, Kryptographie und Kombinatorik beschäftigte. WerdegangRudich promovierte 1989 an der University of California, Berkeley bei Manuel Blum (Limits on the Provable Consequences of One-Way Functions) und war ab Anfang der 1990er Jahre Professor für Informatik an der Carnegie Mellon University. 2007 erhielt er mit Alexander Razborov den Gödel-Preis für die Arbeit Natural Proof, die zeigte, dass Schaltkreiskomplexitätsmethoden zur Bestimmung einer Untergrenze der Komplexität eines Problems wahrscheinlich nicht geeignet sind, das P-NP-Problem zu lösen.[2] Dabei isolierten sie eine gemeinsame Eigenschaft dieser Schaltkreiskomplexitäts-Verfahren, die sie Natural Proof nennen. Sie zeigten, dass ein Natural-Proof-Beweis für das P=NP-Problem zur Folge hätte, dass keine Pseudozufallsgeneratoren existieren, was aber allgemein angenommen wird. Weiter zeigten sie, dass es keine Natural-Proof-Beweise dafür gibt, dass einige bekannte kryptographische Probleme NP-schwer sind (wie die Faktorisierung ganzer Zahlen oder das Problem des diskreten Logarithmus). Die Arbeit von Razborov und Rudich war ein wichtiger Fortschritt im P=NP-Problem, einem der Clay Probleme, der zeigte, dass man in neuen Richtungen nach der Lösung suchen musste. Er war Herausgeber des Journal of Cryptography. Rudich war Amateur-Zauberer. WeblinksEinzelnachweise
|
||||||||||