Zum Inhalt springen

Steven Rudich

aus Wikipedia, der freien Enzyklopädie
Datei:Steven Rudich May 2004.jpg
Steven Rudich, 2004

Steven Rudich (* 4. Oktober 1961; † 29. Oktober 2024<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:|: }}{{#if:|{{#if:Steven Rudich (1961-2024)|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Steven Rudich (1961-2024)}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Steven Rudich (1961-2024)}}}}|[{{#invoke:URLutil|getNormalized|1=https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Steven Rudich (1961-2024)}}}}]}}{{#if:| ({{{format}}}{{#if:computationalcomplexity.org2024-11-11{{#if: 2024-12-11 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:en|de||{{#if:en|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html}}%7C%7C}}}}{{#if:Steven Rudich (1961-2024)|{{#if:{{#invoke:WLink|isValidLinktext|1=Steven Rudich (1961-2024)|lines=0}}||}}}}{{#if: computationalcomplexity.org| In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=computationalcomplexity.org}}}}{{#if: | {{{hrsg}}}{{#if: 2024-11-11|,|{{#if: 2024-12-11 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: 2024-11-11| {{#if:{{#invoke:DateTime|format|2024-11-11|noerror=1}}
            |{{#invoke:DateTime|format|2024-11-11|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=2024-11-11|class=Zitationswartung}} }}{{#if: |,|{{#if: 2024-12-11 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2024-12-11 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:2024-11-11|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:1807490||(?)}}}}}}{{#if: 2024-12-11|;}}}}{{#if: 2024-12-11| {{#if:2024-11-11{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2024-12-11 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2024-12-11|class=Zitationswartung}} }} {{#invoke:DateTime|format|2024-12-11|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:en|de||{{#if:en|1}}}}|{{#if:computationalcomplexity.org2024-11-11{{#if: 2024-12-11 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:en|en|de}}|de||
          {{#invoke:Multilingual|format|en|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:en|en|de}}|de||, }}{{{kommentar}}}}})}}{{#if: 2024-11-11{{#if: 2024-12-11 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}en|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html
      | {{#if:{{#invoke:URLutil|isWebURL|https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html
       | {{#if:{{#invoke:URLutil|isWebURL|https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html
      | {{#if:{{#invoke:URLutil|isWebURL|https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html
       | {{#if:{{#invoke:URLutil|isWebURL|https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://blog.computationalcomplexity.org/2024/11/steven-rudich-1961-2024.html }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref>) war ein US-amerikanischer Informatiker, 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, 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-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

Einzelnachweise

<references />

{{#ifeq: p | p | | {{#if: 173723675n/90/683634233181909 | |

}} }}Vorlage:Hinweisbaustein{{#ifeq: p | p | | {{#if: 173723675n/90/683634233181909 | |

}} }}{{#ifeq:||{{#if: | [[Kategorie:Wikipedia:GND fehlt {{#invoke:Str|left|{{{GNDCheck}}}|7}}]] }}{{#if: | {{#if: | | }} }} }}{{#if: | {{#ifeq: 0 | 2 | | }} }}{{#if: | {{#ifeq: 0 | 2 | | }} }}{{#ifeq: p | p | {{#if: 173723675 | | {{#if: {{#statements:P227}} | | }} }} }}{{#ifeq: p | p | {{#if: 173723675 | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P227}} | | }} }} }} }}{{#ifeq: p | p | {{#if: n/90/683634 | | {{#if: {{#statements:P244}} | | }} }} }}{{#ifeq: p | p | {{#if: n/90/683634 | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P244}} | | }} }} }} }}{{#ifeq: p | p | {{#if: 233181909 | | {{#if: {{#statements:P214}} | | }} }} }}{{#ifeq: p | p | {{#if: 233181909 | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P214}} | | }} }} }} }}Vorlage:Wikidata-Registrierung

{{#if: Rudich, Steven | {{#if: | {{#if: US-amerikanischer Informatiker | {{#if: 4. Oktober 1961 | {{#if: | {{#if: 29. Oktober 2024 | {{#if: |
Personendaten
NAME Rudich, Steven

}}

ALTERNATIVNAMEN

}}

KURZBESCHREIBUNG US-amerikanischer Informatiker

}}

GEBURTSDATUM 4. Oktober 1961

}}

GEBURTSORT

}}

STERBEDATUM 29. Oktober 2024

}}

STERBEORT

}}

Vorlage:Wikidata-Registrierung

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Steven_Rudich&oldid=1807490“