Quelltext der Seite Steven Rudich

[[Datei:Steven Rudich May 2004.jpg|mini|Steven Rudich, 2004]]
'''Steven Rudich''' (* [[4. Oktober]] [[1961]]; † [[29. Oktober]] [[2024]]<ref>{{Internetquelle |url=https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html |titel=Steven Rudich (1961-2024) |autor= |werk=computationalcomplexity.org |datum=2024-11-11 |abruf=2024-12-11 |sprache=en}}</ref>) war ein US-amerikanischer [[Informatik]]er, der sich mit [[Komplexitätstheorie]], [[Kryptographie]] und [[Kombinatorik]] beschäftigte.

== Werdegang ==
Rudich 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.<ref>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, [http://www.mi.ras.ru/~razborov/int.ps Online hier,] Postscript-Datei.</ref> 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-Schwere|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.

== Weblinks ==
*[https://www.cs.cmu.edu/~rudich/ Homepage an der Carnegie Mellon]

== Einzelnachweise ==
<references />

{{Normdaten|TYP=p|GND=173723675|LCCN=n/90/683634|VIAF=233181909}}

{{SORTIERUNG:Rudich, Steven}}
[[Kategorie:Informatiker]]
[[Kategorie:US-Amerikaner]]
[[Kategorie:Geboren 1961]]
[[Kategorie:Gestorben 2024]]
[[Kategorie:Mann]]

{{Personendaten
|NAME=Rudich, Steven
|ALTERNATIVNAMEN=
|KURZBESCHREIBUNG=US-amerikanischer Informatiker
|GEBURTSDATUM=4. Oktober 1961
|GEBURTSORT=
|STERBEDATUM=29. Oktober 2024
|STERBEORT=
}}