¿Cuál es la versión grande de NC?

$\mathsf{NC}$ captura la idea de eficientemente paralelizable, y una interpretación de la misma son los problemas que se pueden resolver en el tiempo usando procesadores paralelos para algunas constantes , . Mi pregunta es si hay una clase de complejidad análoga donde el tiempo es y el número de procesadores es . Como una pregunta para completar el espacio en blanco: $O(\log^c n)$ $O(n^k)$ $c$ $k$ $n^c$ $2^{n^k}$

$\mathsf{NC}$ es a como _ _ es a $\mathsf{P}$ $\mathsf{EXP}$

En particular, estoy interesado en un modelo donde tenemos un número exponencial de computadoras dispuestas en una red con un grado polinomialmente limitado (digamos que la red es independiente de la entrada / problema o al menos de alguna manera fácil de construir, o cualquier otra suposición de uniformidad razonable ) En cada paso de tiempo:

Cada computadora lee el número polinómico de mensajes de tamaño polinómico que recibió en el paso de tiempo anterior.
Cada computadora ejecuta algunos cálculos de polytime que pueden depender de estos mensajes.
Cada computadora pasa un mensaje (de polylength) a cada uno de sus vecinos.

¿Cuál es el nombre de una clase de complejidad correspondiente a este tipo de modelos? ¿Cuál es un buen lugar para leer sobre tales clases de complejidad? ¿Hay algún problema completo para tal clase?

cc.complexity-theory reference-request complexity-classes circuit-complexity dc.parallel-comp Artem Kaznatcheev
fuente

pregunta relacionada, creo: cstheory.stackexchange.com/q/2788/1037

Artem Kaznatcheev

Tenemos , , , . Entonces, la clase correspondiente a podría ser algo así como y luego la clase correspondiente a será . Es solo una manipulación algebraica, no he comprobado si cumple con sus requisitos, pero creo que satisfará las tres condiciones, pero no tendrá exponencialmente muchas computadoras. Creo que de lo contrario deberías abandonar ese requisito (más)

N C^{k} = A S p a c e T i m e (O (\log n), (\log n)^{k})

$NC^k = ASpaceTime(O(\log n), (\log n)^k)$

N C = A S p a c e T i m e (O (\log n), (\log n)^{O (1)})

$NC = ASpaceTime(O(\log n), (\log n)^{O(1)})$

P = T i m e (n^{O (1)})

$P = Time(n^{O(1)})$

E X P = T i m e (2^{n^{O (1)}})

$EXP = Time(2^{n^{O(1)}})$

N C^{k}

$NC^k$

A S p a c e T i m e (n^{O (1)}, 2^{O (\log n)^{k}})

$ASpaceTime(n^{O(1)}, 2^{O(\log n)^k})$

N C

$NC$

A S p a c e T i m e (n^{O (1)}, 2^{(\log n)^{O (1)}})

$ASpaceTime(n^{O(1)}, 2^{(\log n)^{O(1)}})$

Kaveh

la clase resultante contendrá y la analogía no dará como .

E X P

$EXP$

N C \subseteq P

$NC \subseteq P$

Kaveh

No entiendo de dónde sacaste como la complejidad del espacio. Hasta donde yo sé, permite polinomialmente muchas puertas. Si queremos seguir las líneas de su análogo, entonces deberíamos ver como y luego la clase de complejidad que estoy buscando es algo así como . Sin embargo, esperaba que haya una mejor caracterización que esto.

l o g n

$log n$

N C

$NC$

N C

$NC$

P T / W K (l o g^{c} n, n^{k}) / p o l y

$PT/WK(log^c n,n^k)/poly$

P T / W K (n^{c}, 2^{n^{k}}) / p o l y

$PT/WK(n^c ,2^{n^k})/poly$

Artem Kaznatcheev

Eso es estándar (aunque no está en Complexity Zoo), verifique, por ejemplo, Ruzzo, "Sobre la complejidad del circuito uniforme", 1981. Además, creo que debería trabajar con clases uniformes, cada función tiene alternancia de tamaño exponencial / circuitos lógicos de profundidad 2 (y esto satisfará las tres condiciones si usamos fan-in acotado y profundidad ). Y como dije, si hay exponencialmente muchos nodos, entonces la analogía no se cumple. También una propiedad principal de la computación paralela es ahorrar tiempo, por ejemplo, es tiempo de poli-log en el caso de . Creo que el tiempo cuasi polinomial correspondería al tiempo poli-log.

\log n

$\log n$

N C

$NC$

Kaveh

Respuestas:

Creo que la clase que estás buscando es . Suponga que tiene procesadores que cumplen los requisitos: $PSPACE$ $exp(n^k) = 2^{O(n^k)}$

Cada computadora lee el número polinómico de mensajes de tamaño polinómico que recibió en el paso de tiempo anterior.

Cada computadora ejecuta algunos cálculos de polytime que pueden depender de estos mensajes.

Cada computadora pasa un mensaje (de polylength) a cada uno de sus vecinos.

Esto se puede modelar al tener un circuito con capas de , donde cada capa tiene "compuertas" , y cada "compuerta" realiza un cálculo de tiempo polinómico (que satisface la parte 2) con una entrada de polinomio ( satisfaciendo la parte 1), y tiene un despliegue polinómico (satisfaciendo la parte 3). $poly(n)$ $exp(n^k)$

Dado que cada puerta calcula una función de tiempo polinomial, cada una de ellas puede ser reemplazada por un circuito de tamaño polinómico (con AND / OR / NOT) de la manera habitual. Tenga en cuenta que las entradas y salidas de polinomiales se pueden hacer que sean 2, aumentando solo la profundidad en un factor . Lo que queda es un circuito uniforme de profundidad de con compuertas AND / OR / NOT. Este es precisamente el tiempo polinómico alterno, que es precisamente . $O(\log n)$ $poly(n)$ $exp(n^k)$ $PSPACE$

Ryan Williams
fuente

Ryan, no entiendo cómo estás colocando el número exponencial de computadoras en muchas capas polinomiales, me parece que la profundidad puede ser exponencial, ¿podrías explicar un poco más por qué esto es posible? También me parece que la construcción trivial del circuito CNF de una función arbitraria dada como un circuito fan-in 2 satisfaría los requisitos, ¿me estoy perdiendo algo?

Kaveh

@Kaveh: No entiendo tu primera pregunta. Sobre el segundo, aunque hay un circuito de profundidad-2 de tamaño exponencial para cualquier función, NC (poly) requiere que pueda generar los circuitos de manera uniforme, por lo que no puede producir circuitos arbitrarios para cada tamaño de entrada.

Robin Kothari

@ Robin, gracias. Probablemente estoy confundiendo cosas. (Siento que la profundidad de los circuitos correspondientes a PSpace debería ser exponencial, también creo que PSpace es EXP ya que L es a P, por lo que decir lo mismo cuando L es reemplazado por NC es extraño para mí, siento que la clase en la que estamos cuidar debe estar entre PSpace y EXP.) Tengo que pensar un poco más para entender lo que está sucediendo aquí.

Kaveh

@Kaveh, asigné el número de capas (es decir, la profundidad) para que sea exponencial, por lo que la profundidad no puede ser exponencial, por definición. Hay exponencialmente muchos procesadores, por lo que su CNF necesitará un despliegue exponencial, violando una de las condiciones. La profundidad de los circuitos de tamaño exponencial correspondiente a PSPACE es polinómica. La razón por la que esto es cierto, y la razón por la que ambas analogías son "válidas" en cierto sentido ("PSPACE es EXP como L es hacia P" y "PSPACE es EXP como NC es hacia P") es porque PSPACE = Polinomio alterno Hora. No sabemos si L = Tiempo logarítmico alterno (esto es NC1).

Ryan Williams

Creo que entiendo mejor la situación después de leer sus comentarios y los de Robin, gracias.

Kaveh

Como dice Ryan, esta clase es PSPACE. Esta clase a menudo se llama NC (poli) en la literatura. Aquí hay una cita directa del documento QIP = PSPACE :

Consideramos una variante ampliada de NC, que es la clase de complejidad NC (poli) que consiste en todas las funciones computables por familias uniformes de espacio polinomial de circuitos booleanos que tienen profundidad polinómica. (La notación NC (2 ^poli ) también se ha utilizado previamente para esta clase [11].) Para problemas de decisión, se sabe que NC (poli) = PSPACE [10].

[10] A. Borodin. Sobre relacionar el tiempo y el espacio con el tamaño y la profundidad. SIAM Journal on Computing, 6: 733–744, 1977.

[11] A. Borodin, S. Cook y N. Pippenger. Cálculo paralelo para anillos bien dotados y máquinas probabilísticas con espacio limitado. Información y control, 58: 113–136, 1983.

Una forma de ver esto es probar ambas inclusiones directamente. Para ver que NC (poli) está en PSPACE, tenga en cuenta que podemos calcular la salida de la puerta final de forma recursiva, y solo necesitaremos una pila de tamaño igual a la profundidad del circuito, que es polinomial. Para mostrar que PSPACE está en NC (poli), tenga en cuenta que QBF, que está completo en PSPACE, puede escribirse como un circuito de profundidad polinomial con exponencialmente muchas puertas de la manera habitual: el cuantificador existente es una puerta OR, el cuantificador total Es una puerta AND. Dado que solo hay polinomialmente muchos cuantificadores, este es un circuito de profundidad polinomial.

Robin Kothari
fuente