¿Está contenido el RNC uniforme en el espacio polylog?

28

Log-space-uniform NC está contenido en un espacio polylog determinista (a veces escrito PolyL). ¿Log-space-uniform RNC también está en esta clase? La versión aleatoria estándar de PolyL debería estar en PolyL, pero no veo que el RNC (uniforme) esté en PolyL aleatorizado.

La dificultad que veo es que en RNC, el circuito puede "mirar los bits aleatorios" todo lo que quiera; es decir, las entradas aleatorias pueden tener un despliegue arbitrario. Pero en la versión aleatoria de PolyL, no es como si obtuvieras una cinta de bits aleatorios que puedes ver todo lo que quieras; más bien, solo puedes lanzar una moneda en cada paso de tiempo.

¡Gracias!

Ryan O'Donnell
fuente
44
Periklis Papakonstantinou me ha enviado exactamente el tipo de respuesta que estaba buscando. Me dijo que Valentine Kabanets le dijo que uno puede usar Kabanets - Impagliazzo para mostrar que el uniforme-RNC en PolyL implicaría ciertos límites inferiores del circuito para NEXP o Permanente. Quizás uno de ellos podría publicar el argumento aquí.
Ryan O'Donnell
2
Corolario 4.13 en el periódico
sdcvvc
@sdvvc: ¿Hacer eso una respuesta?
Joshua Grochow
@JoshuaGrochow Sabemos que no es posible. Sin embargo, ¿es posible R N C = P = B P P = N P = P S P A C E ? NC=PSPACERNC=P=BPP=NP=PSPACE
T ....

Respuestas:

18

Quizás la mayoría de la gente piensa que (o incluso que R N C = N C ), pero soy escéptico sobre esto (vea la segunda parte de mi Responda abajo). Si R N C está contenido en D S P A C E ( p o l y l o g ) , entonces también está contenido en NRNCDSPACE(polylog)RNC=NCRNCDSPACE(polylog) (más específicamente, está en D T I M E ( 2 p o l y l o g ) por búsqueda exhaustiva).NTIME(2polylog)DTIME(2polylog)

Valentine Kabanets me explicó el siguiente argumento (folklore) de su trabajo con Russell Impagliazzo que explica por qué es poco probable.RNCNTIME(2polylog)

Teorema: si , entonces N E X P no es computable por circuitos booleanos de tamaño o ( 2 n / n ) (es decir, submáximo por Shannon; irrelevante, pero vea a Lupanov para la tensión), o permanente no es computable mediante fórmulas aritméticas (sin división) sobre Z de tamaño cuasipolinomial.RNCNTIME(2polylog)NEXPo(2n/n)Z

Prueba: suponga . Si permanente tiene una fórmula de tamaño cuasipolinomial, entonces podemos adivinar y verificar dicha fórmula para permanente utilizando un probador de identidad polinomial de tiempo cuasipolinomial por supuesto. Esto coloca Permanente en N T I M E ( 2 p o l y l o g ) .RNCNTIME(2polylog)NTIME(2polylog)

Según el teorema de Toda, también está en N T I M E ( 2 p o l y l o g ) . Por relleno, la versión de tiempo lineal-exponencial de Σ 5 está también en N E X P . Por lo tanto, la versión exponencial lineal de Σ 5 tiene un circuito de tamaño o ( 2 n / n ) (es decir, submax). Pero, mediante un simple argumento de diagonalización, se puede mostrar que la versión exponencial lineal de Σ 5Σ2NTIME(2polylog)Σ5NEXPΣ5o(2n/n)Σ5requiere un tamaño máximo de circuito, lo cual es una contradicción (por cierto, esta es una variante de una pregunta de nivel medio para un curso de complejidad de nivel de posgrado; bueno, tal vez probar que requiere circuitos de tamaño máximo es más simple) QEDEXPSPACE

Ahora la dirección impopular.

RNC

(También hay un par de otros documentos, como el maravilloso documento de Noam Nisan sobre aleatoriedad de lectura única versus lectura múltiple, que muestran cómo comprar un error de dos lados con un error de un solo lado).

Por cierto, comprender cómo construir PRG engañando modelos de cómputo delimitados por el espacio con múltiples accesos a su entrada (por ejemplo, longitudes lineales Bps) también está muy relacionado con esta pregunta.

- Periklis

usuario17164
fuente
"error de dos lados para error de cero".
user17164