¿Cuál es la motivación detrás de la definición de pseudoaleatorio en Nisan / Wigderson?

Estoy leyendo el clásico "Dureza contra aleatoriedad" de Nisan y Wigderson. Deje , y arregle una función . Definen una familia de funciones para ser pseudoaleatoria en el caso de cada circuito de tamaño que tengamos$B=\{0,1\}$$l\colon \mathbb{N} \to \mathbb{N}$$G = \{G_n : B^{l(n)} \to B^n\}$$n$

$(*) \ \ | P(C(x) = 1) - P(C(G(y))=1) | < 1/n$

(donde son variables aleatorias uniformes).$x \in B^{n},y \in B^{l(n)}$

Yo entiendo que soy a pensar en e como variables aleatorias, y que yo quiero comparar la distancia entre y como variables aleatorias. Tengo la intuición de que los circuitos se están utilizando como una especie de "pruebas" para ver si puede ser "descubierto". Con lo que realmente estoy luchando es por qué la condición es la correcta. ¿Alguien tiene algún consejo sobre cómo pensar en esta definición?y $x$$y$$x$$G(y)$$G$$(*)$

Hay dos aspectos que deben mencionarse.

La primera es la idea general de definir un PRG haciendo que su salida se vea diferente de los circuitos uniformes a pequeños . Esta idea se remonta a Yao y es realmente la definición más fuerte posible que se puede pedir al apuntar explícitamente a la pseudoaleatoriedad para los observadores computacionalmente delimitados .

El segundo aspecto es la elección de parámetros en los que limitamos el tamaño del circuito a y la diferencia de probabilidad de aceptación en , donde es también el tamaño de salida PRG. Esta elección es algo diferente de la criptografía habitual, donde el tamaño del circuito es y la diferencia de probabilidad debe ser menor que cualquier . En nuestro caso, parámetros específicos (en lugar de$n$$1/n$$n$$poly(n)$$poly(n)$$poly(n)$) eran necesarios para obtener los mejores resultados, incluidas, en particular, las simulaciones polinómicas. Si bien, en principio, uno podría tener 3 parámetros diferentes, resultó que nuestros resultados tenían estos trabajando esencialmente de la misma manera, por lo que los doblamos a uno solo (además del tamaño de entrada que se veía como una función de )$l(n)$$n$

De ninguna manera soy un experto en esto, pero un componente clave de la definición de pseudoaleatoriedad (en oposición a los intentos de definir la aleatoriedad) es que el objetivo de algo "pseudoaleatorio" es engañar a un circuito. En otras palabras, la motivación es pensar en la cadena pseudoaleatoria que se suministra al circuito en lugar de la cadena verdaderamente aleatoria.

En ese sentido, no es realmente que estés tratando de fingir que y "se ven igual". Es que "se ven iguales" a un circuito (de complejidad necesariamente limitada).$x$$G(y)$

Por lo tanto, el papel del circuito es crucial, en lugar de ser simplemente una "función de prueba".

Con suerte, puedo ampliar un poco la respuesta de Suresh. Primero, no creo que la rigurosidad de la desigualdad sea necesaria en su , y tampoco estoy seguro de por qué se necesita , y no o algo más. Sin embargo, prácticamente, creo que 1 / n es suficiente para obtener algunos resultados teóricos interesantes.$(*)$$1/n$$1/2n$

Pero entonces seguramente querrá afirmar que cada es computable en una cierta cantidad de tiempo, digamos exponencial. Además, creo que tendrá que afirmar que . Puedes pensar en como la longitud de la semilla. Por tanto, es pseudoaleatorio si puede aumentar el número de bits en una cadena aleatoria de longitud sin ser detectado por un circuito de tamaño menor que .$G_i$$l(n) < n$$l(n)$$G_i$$l(n)$$n$