Steven Rudich , született1961. október 4, egy amerikai számítógép-elméleti szakember, aki a komplexitáselmélet , a kriptográfia és a kombinatorika területén dolgozik .
Rudich szerzett PhD 1989 a University of California, Berkeley felügyelete alatt Manuel Blum ( „Követelmények a kimutatható következményei Egyirányú funkciók ”). Az 1990-es évek eleje óta a Carnegie-Mellon Egyetem informatika professzora .
2007-ben Alexandre Razborovval együtt megkapta a Gödel-díjat . a Natural Proof cikkükhöz , ahol bebizonyosodik, hogy az áramkör komplexitásában alkalmazott redukciós módszerek valószínűleg nem alkalmasak a P = NP probléma megoldására . Ehhez kiemelik az áramkör komplexitáscsökkentés összes bizonyítékának közös tulajdonságait, és az ilyen tulajdonságokkal rendelkező bizonyításokat természetes bizonyítékoknak nevezik . Megmutatták, hogy a P = NP probléma természetes bizonyítéka azt jelentené, hogy nincsenek pszeudo-véletlen generátorok, amelyek létezése általában elfogadott. Végül bizonyítják, hogy nincs természetes bizonyíték annak megállapítására, hogy bizonyos ismert kriptográfiai problémák (például a természetes egészek faktorizálása vagy a diszkrét logaritmusprobléma) NP-nehézek . Rudich egyben társszerzője annak a cikknek, amely bebizonyítja, hogy az NP-teljes problémák még az AC 0 vagy NC 0 osztály csökkentése alatt is fennmaradnak .
Rudich 1991 óta szervez nyári oktatási programot középiskolások számára . A foglalkozások reggel az elméleti informatika különböző szempontjaival foglalkoznak, délután pedig fakultatív tevékenységekkel egészülnek ki: robotika, programozás, matematika. A felvétel vizsga alapján történő kiválasztással történik, az úgynevezett érdeklődési teszt . Ezt a hét hetes, korábban Andrew's Leap néven futó nyári programot ma Leap @ CMU- nak hívják .
Rudich amatőr varázsló is.