Steven Rudich , født den4. oktober 1961, er en amerikansk datamaskinteoretiker som jobber med kompleksitetsteori , kryptografi og kombinatorikk .
Rudich fikk en doktorgrad i 1989 fra University of California i Berkeley under tilsyn av Manuel Blum ( "Limits on the Provable Consequences of One-Way Functions "). Han har vært professor i informatikk ved Carnegie-Mellon University siden tidlig på 1990-tallet .
I 2007, sammen med Alex Razborov , fikk han den Gödel Prize . for deres Natural Proof- artikkel , hvor det er vist at reduksjonsmetodene som brukes i kretskompleksitet sannsynligvis ikke er egnet for å løse P = NP-problemet . For dette fremhever de egenskaper som er felles for alle bevisene for kretskompleksitetsreduksjon, og de kaller bevisene med disse egenskapene for naturlige bevis . De viser at et naturlig bevis på problemet P = NP ville antyde at det ikke er noen pseudo-tilfeldige generatorer, eksistens som peiling er generelt innrømmet. Til slutt demonstrerer de at det ikke er noe naturlig bevis for å fastslå at visse kjente kryptografiske problemer (for eksempel faktorisering av naturlige heltall eller det diskrete logaritmeproblemet) er NP-vanskelige . Rudich er også medforfatter av en artikkel som beviser at NP-komplette problemer forblir så selv under reduksjon av klasse AC 0 eller NC 0 .
Rudich har organisert et sommerutdanningsprogram siden 1991 for videregående studenter . Kursene tar for seg ulike aspekter av teoretisk informatikk om morgenen, og suppleres med valgfrie aktiviteter på ettermiddagen: robotikk, programmering, matematikk. Opptak skjer ved utvelgelse ved eksamen som kalles interessetest . Dette syv ukers sommerprogrammet, tidligere kalt Andrew's Leap , heter nå Leap @ CMU .
Rudich er også en amatørtrollmann.