Steven Rudich , născut pe4 octombrie 1961, este un teoretician american al computerului care lucrează în teoria complexității , criptografie și combinatorică .
Rudich a obținut un doctorat în 1989 de la Universitatea din California la Berkeley sub supravegherea lui Manuel Blum ( „Limitele consecințelor dovedibile ale funcțiilor unidirecționale ”). A fost profesor de informatică la Universitatea Carnegie-Mellon de la începutul anilor '90 .
În 2007, alături de Alexandre Razborov , a primit Premiul Gödel . pentru articolul lor Natural Proof , unde se arată că metodele de reducere utilizate în complexitatea circuitului nu sunt probabil potrivite pentru rezolvarea problemei P = NP . Pentru aceasta, ele evidențiază proprietăți comune tuturor dovezilor de reducere a complexității circuitului și numesc probele cu aceste proprietăți dovezi naturale . Acestea arată că o dovadă naturală a problemei P = NP ar implica faptul că nu există generatori pseudo-aleatori, existență care este admisă în general. În cele din urmă, ei demonstrează că nu există nicio dovadă naturală care să stabilească faptul că anumite probleme criptografice cunoscute (cum ar fi factorizarea numerelor întregi naturale sau problema logaritmului discret) sunt NP-dificile . Rudich este, de asemenea, coautorul unui articol care demonstrează că problemele NP-complete rămân așa chiar și sub o reducere a clasei AC 0 sau NC 0 .
Rudich organizează un program de educație de vară din 1991 pentru elevii de liceu . Cursurile tratează diverse aspecte ale informaticii teoretice dimineața și sunt completate de activități opționale după-amiaza: robotică, programare, matematică. Admiterea se face prin selecție prin examen numit test de interes . Acest program de vară de șapte săptămâni, numit anterior Andrew's Leap , se numește acum Leap @ CMU .
Rudich este, de asemenea, un conjurator amator.