Deje ser una constante. ¿Cómo podemos construir de manera comprobable un generador pseudoaleatorio que engañe a los autómatas finitos de estado d ?
Aquí, una -state autómatas finitos tiene d nodos, un nodo de inicio, un conjunto de nodos que representan aceptar estados, y dos bordes dirigidos etiquetados 0, 1 que sale de cada nodo. Cambia de estado de forma natural a medida que lee la entrada. Dado un ϵ , encuentre f : { 0 , 1 } k → { 0 , 1 } n tal que para cada autómata finito de estado d que calcule alguna función A ,
Aquí denota la distribución uniforme en k variables, y queremos que k sea lo más pequeño posible (por ejemplo, log n ). Estoy pensando en que d está en el orden de n , aunque también podemos hacer la pregunta de manera más general (por ejemplo, ¿el número de bits necesarios crecería con n ?).
Algunos antecedentes
La construcción de generadores pseudoaleatorios es importante en la des aleatorización, pero el problema general (PRG para algoritmos de tiempo polinomial) hasta ahora ha resultado demasiado difícil. Sin embargo, ha habido avances en los PRG para el cálculo del espacio acotado. Por ejemplo, este documento reciente ( http://homes.cs.washington.edu/~anuprao/pubs/spaceFeb27.pdf ) ofrece un límite de aproximadamente para programas de ramificación regulares de lectura única. La pregunta con los programas generales de ramificación de lectura única todavía está abierta (con k = log n ), por lo que me pregunto si se conoce la respuesta para esta simplificación. (Un autómata finito es como un programa de ramificación de lectura única en el que cada capa es la misma).
Respuestas:
fuente
RJlipton también cita esta prueba aparentemente igual en su blog "la garantía del generador Nisans" . la prueba aparentemente se origina en el documento ¿Qué tan fuerte es el generador pseudoaleatorio de Nisan? David, Papakonstantinou, Sidiropoulos (2010). También tenga en cuenta una pregunta casi más profunda y los mejores límites están vinculados con una separación de clase de mayor complejidad:
fuente