Algunas preguntas sobre computación paralela y la clase NC

14

Tengo varias preguntas relacionadas sobre estos dos temas.

En primer lugar, la mayoría de los textos de complejidad sólo pasan por alto la clase NC . ¿Existe un buen recurso que cubra la investigación más en profundidad? Por ejemplo, algo que discute todas mis preguntas a continuación. Además, supongo que todavía ve una buena cantidad de investigación debido a su vínculo con la paralelización, pero podría estar equivocado. La sección en el zoológico de complejidad no es de mucha ayuda.NC

Segundo, el cálculo sobre un semigrupo está en si suponemos que la operación del semigrupo toma tiempo constante. Pero, ¿qué pasa si la operación no toma un tiempo constante, como es el caso de los enteros ilimitados? ¿Hay algún problema conocido de -complete?NC1NCi

Tercero, desde , ¿hay algún algoritmo para convertir cualquier algoritmo de espacio de registro en una versión paralela?LNC2

Cuarto, parece que la mayoría de la gente supone que de la misma manera que . ¿Cuál es la intuición detrás de esto?NCPPNP

Quinto, cada texto que he leído menciona la clase pero no da ejemplos de problemas que contiene. ¿Hay alguna?RNC

Finalmente, esta respuesta menciona problemas en con tiempo de ejecución paralelo sublineal. ¿Cuáles son algunos ejemplos de estos problemas? ¿Hay otras clases de complejidad que contienen algoritmos paralelos que no se sabe que están en ?PNC

Mike Izbicki
fuente
1
Además, tenga en cuenta esta pregunta similar.
Nicholas Mancuso

Respuestas:

9

Tercero, desde , ¿hay algún algoritmo para convertir algún algoritmo de espacio de registro en una versión paralela?LNC2

Puede mostrarse (libro de texto de Arora y Barak) dado un -tiempo TM M , que un TM M ' inconsciente (es decir, un TM cuyo movimiento de la cabeza es independiente de su entrada x ) puede construir un circuito C n para calcular M ( x ) donde | x | = n .t(norte)METROMETROXCnorteMETRO(X)El |XEl |=norte

El bosquejo de la prueba está en la línea de hacer que simule M y defina "instantáneas" de su estado (es decir, posiciones de las cabezas, símbolos en las cabezas) en cada paso de tiempo t i (piense en un registro computacional). Cada paso t i se puede calcular a partir de x y el estado t i - 1 . Debido a que cada instantánea involucra solo una cadena de tamaño constante, y solo existe una cantidad constante de cadenas de ese tamaño, la instantánea en t i puede ser calculada por un circuito de tamaño constante.METROMETROtyotyoXtyo-1tyo

Si compones los circuitos de tamaño constante para cada , tenemos un circuito que calcula M ( x ) . Usando este hecho, junto con la restricción de que el lenguaje de M está en L , vemos que nuestro circuito C n es, por definición, logspace-uniform , donde uniformidad solo significa que nuestros circuitos en nuestra familia de circuitos { C n } computan M ( x ) Todos tienen el mismo algoritmo. No es un algoritmo personalizado para cada circuito que opera en el tamaño de entrada n .tyoMETRO(X)METROLCnorte{Cnorte}METRO(X)norte

Nuevamente, a partir de la definición de uniformidad, vemos que los circuitos que deciden cualquier lenguaje en deben tener un tamaño de función ( n ) computable en O ( log n ) . La familia de circuitos A C 1 tiene como máximo O ( log n ) de profundidad.LTalla(norte)O(logn).AC1O(logn)

Finalmente se puede demostrar que da la relación en cuestión.AC1NC2

En cuarto lugar, parece que la mayoría de la gente asume que de la misma manera que PN P . ¿Cuál es la intuición detrás de esto?NCPPNP

Antes de seguir adelante, definamos qué significa completitud.P

Un lenguaje es P -completo si L P y cada lenguaje en P es espacio de registro reducible a él. Además, si L es P -completo, entonces se cumple lo siguienteLPLPPLP

  1. LNCP=NC

  2. LLP=L

Ahora consideramos que es la clase de idiomas eficientemente decidida por una computadora paralela (nuestro circuito). Hay algunos problemas en P que parecen resistir cualquier intento de paralelización (es decir, programación lineal y problema de valor de circuito). Es decir, ciertos problemas requieren que el cómputo se realice paso a paso.NCP

Por ejemplo, el problema del valor del circuito se define como:

Dado un circuito , una entrada xy una puerta g C , ¿cuál es la salida de g en C ( x ) ?CxgCgC(x)

No sabemos cómo calcular esto mejor que calcular todas las puertas que vienen antes de g . Dado que algunos de ellos pueden calcularse en paralelo, por ejemplo, si todos ocurren en algún paso de tiempo t i , pero no sabemos cómo calcular la salida de las puertas en el paso de tiempo t i y el paso de tiempo t i + 1 para la dificultad obvia que las puertas en t i + 1 requieren la salida de las puertas en t i !ggtititi+1ti+1ti

Esta es la intuición detrás de .NCP


Limits to Parallel Computation es un libro sobre -Completeness en la misma línea del libro N P -Completeness de Garey & Johnson .PNP

Nicholas Mancuso
fuente
Gracias por las 2 referencias y la respuesta parcial. El libro Los límites de la computación paralela funciona mejor que los otros libros que he visto, pero aún es relativamente antiguo y no es tan completo como me gustaría.
Mike Izbicki
3

Quinto, cada texto que he leído menciona la clase RNC pero no da ejemplos de problemas que contiene. ¿Hay alguna?

El documento "Matching is as Easy as Matrix Inversion" de Mulmuley, Vazirani y Vazirani tiene varios ejemplos de problemas en la clase . El principal es encontrar una coincidencia máxima, luego reducen otros problemas a este.RNC2

Mike Izbicki
fuente