Generadores pseudoaleatorios

Question

¿Ha habido algún progreso sobre la construcción de generadores pseudoaleatorios fuertes?

No soy un experto en este tema, básicamente todo lo que sé es una definición de un generador pseudoaleatorio, la idea de que están relacionados con las funciones unidireccionales, así como otras piezas estándar de teoría de la complejidad.

Apreciaré cualquier información relacionada, por ejemplo, lo que es equivalente a.

Answer 1

Ilya,

Es posible que estoy interpretando mal lo que estás haciendo (desde los teóricos de la complejidad, aplicado criptógrafos, y combinatorialists todos tienden a un uso ligeramente diferentes definiciones de "pseudo aleatorios"), pero a partir de una teoría del punto de vista, creo que la pregunta está casi resuelto, y lo ha sido por un tiempo.

Como usted ha mencionado, PRNGs están relacionados con funciones solo. En particular, es fácil ver que un PRNG de inmediato le proporciona una vía de función; basta con conectarlo en algunos parámetros iniciales y ejecutar el generador! De ahí la implicación a la P \neq NP; una forma de la función es claramente duro-en-media, y un duro en función promedio es claramente duro en el peor de los casos.) Fue una larga abra problema si lo contrario fuera cierto, si se podría construir un PRNG a partir de la forma de la función. Hace aproximadamente una década, Hastad, Impagliazzo, Levin y Luby respondió a esta pregunta de forma afirmativa en un enorme y técnicamente difícil de papel. La COLINA de la construcción es muy ineficiente, pero a partir de una teoría del punto de vista, es muestra de que la cuestión de la existencia de PRNGs es equivalente a la existencia de una forma de funciones.

Si quieres un PRNG lo suficientemente fuerte como para derandomize BPP, la pregunta en realidad se convierte en un poco más fácil, y ciertamente menos técnica. En el supuesto de que existe algún problema en E requiere exponencial-el tamaño de los circuitos, Impagliazzo y Wigderson construir un generador. (El I-W de papel es fantástico-una lectura esencial para cualquier persona interesada en derandomization.) También sabe que esto es esencialmente lo mejor que podemos hacer, en que derandomizing BPP se requiere probar el circuito de cotas inferiores para el Correo, o mostrando que una de las varias cosas que nadie cree realmente es cierto. (E. g., P = NP.) Este es un resultado de creo que Kabanets y alguien en {Impagliazzo, Wigderson, Goldreich}, aunque no puedo recordar o encontrar el papel.