Steven Rudich , nascido em4 de outubro de 1961, É um americano teórico computador que trabalha na complexidade teoria , criptografia e combinatória .
Rudich obteve um PhD em 1989 na Universidade da Califórnia em Berkeley, sob a supervisão de Manuel Blum ( "Limites nas consequências prováveis das funções unilaterais "). Ele é professor de ciência da computação na Carnegie-Mellon University desde o início dos anos 1990 .
Em 2007, junto com Alexandre Razborov , recebeu o Prêmio Gödel . para seu artigo Natural Proof , onde é mostrado que os métodos de redução empregados na complexidade do circuito provavelmente não são adequados para resolver o problema P = NP . Para isso, destacam propriedades comuns a todas as provas de redução da complexidade de circuitos, e chamam as provas com essas propriedades de provas naturais . Eles mostram que uma prova natural do problema P = NP implicaria que não existem geradores pseudo-aleatórios, existência essa que é geralmente admitida. Finalmente, eles demonstram que não há prova natural para estabelecer que certos problemas criptográficos conhecidos (como a fatoração de inteiros naturais ou o problema do logaritmo discreto) são NP-difíceis . Rudich também é co-autor de um artigo que prova que problemas NP-completos permanecem assim mesmo sob uma redução da classe AC 0 ou NC 0 .
Rudich tem organizado um programa de educação de verão desde 1991 para alunos do ensino médio . As aulas abordam vários aspectos da ciência da computação teórica pela manhã e são complementadas por atividades opcionais à tarde: robótica, programação, matemática. A admissão é feita por seleção por exame denominado teste de interesse . Este programa de verão de sete semanas, anteriormente denominado Andrew's Leap , agora é denominado Leap @ CMU .
Rudich também é um mágico amador.