Russell Graham Impagliazzo es profesor de informática en la Universidad de California en San Diego y se especializa en teoría de la complejidad computacional . Obtuvo un doctorado de la Universidad de California, Berkeley . Su asesor fue Manuel Blum . Es miembro del Guggenheim de 2004 .
Russell Impagliazzo |
---|
Las contribuciones de Impagliazzo a la teoría de la complejidad incluyen: la construcción de un generador de números pseudoaleatorios a partir de cualquier función unidireccional , su prueba del lema XOR de Yao a través de "conjuntos de núcleo duro", su trabajo sobre la ruptura da como resultado la complejidad de la prueba proposicional, como el tamaño exponencial límite inferior para las pruebas de Hilbert de profundidad constante del principio de casillero y la introducción del sistema de cálculo polinomial, su trabajo sobre las conexiones entre la dureza computacional y la desaleatorización, y el trabajo reciente [ cita requerida ] sobre la construcción de fuentes múltiples extractores sin semillas.
Impagliazzo ha contribuido a más de 40 artículos sobre temas dentro de sus especialidades. También planteó la hipótesis del tiempo exponencial de que el 3-SAT no se puede resolver en tiempo subexponencial en el número de variables. Esta hipótesis se utiliza para deducir muchos límites inferiores de algoritmos en informática .
Sus "cinco mundos" son bien conocidos en la teoría de la complejidad computacional .