Steven Rudich
Steven Rudich (* 4. Oktober 1961) ist ein US-amerikanischer Informatiker, der sich mit Komplexitätstheorie, Kryptographie und Kombinatorik beschäftigt.
Rudich promovierte 1989 an der University of California, Berkeley bei Manuel Blum (Limits on the Provable Consequences of One-Way Functions) und ist seit 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.[1] Dabei isolieren 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 ist Herausgeber des Journal of Cryptography.
Rudich ist Amateur-Zauberer.
Weblinks
Einzelnachweise
- Razborov, Rudich: Natural Proof. Journal of Computer and System Sciences, Bd. 55, 1997, S. 24–35 und Proc. 26. Int. ACM Symposium on the Theory of Computing (STOC), 1994, S. 204, Online hier, Postscript-Datei.