- 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 Arbeit Natural Proof, die zeigte, das 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, das 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, das 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 Postcript Datei
Kategorien:- Informatiker
- Geboren 1961
- US-Amerikaner
- Mann
Wikimedia Foundation.
