Steven Rudich , nacido el4 de octubre de 1961, Es un estadounidense teórico equipo que trabaja en la teoría de la complejidad , la criptografía y la combinatoria .
Rudich obtuvo un doctorado en 1989 de la Universidad de California en Berkeley bajo la supervisión de Manuel Blum ( "Límites de las consecuencias demostrables de las funciones unidireccionales "). Ha sido profesor de informática en la Universidad Carnegie-Mellon desde principios de la década de 1990 .
En 2007, junto con Alexandre Razborov , recibió el Premio Gödel . para su artículo Natural Proof , donde se muestra que los métodos de reducción empleados en la complejidad del circuito probablemente no son adecuados para resolver el problema P = NP . Para ello, destacan propiedades comunes a todas las pruebas de reducción de complejidad de circuitos, y llaman a las pruebas con estas propiedades pruebas naturales . Demuestran que una prueba natural del problema P = NP implicaría que no existen generadores pseudoaleatorios, cuya existencia se admite generalmente. Finalmente, demuestran que no existe una prueba natural para establecer que ciertos problemas criptográficos conocidos (como la factorización de enteros naturales o el problema del logaritmo discreto) sean NP-difíciles . Rudich es también coautor de un artículo que prueba que los problemas NP-completos siguen siendo así incluso con una reducción de la clase AC 0 o NC 0 .
Rudich ha estado organizando un programa de educación de verano desde 1991 para estudiantes de secundaria . Las clases tratan diversos aspectos de la informática teórica por la mañana, y se complementan con actividades opcionales por la tarde: robótica, programación, matemáticas. La admisión se realiza mediante selección mediante examen llamado prueba de interés . Este programa de verano de siete semanas, anteriormente llamado Andrew's Leap , ahora se llama Leap @ CMU .
Rudich también es un prestidigitador aficionado.