Clase NC

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 31 de mayo de 2020; las comprobaciones requieren 8 ediciones .

En la teoría de la complejidad computacional, la clase NC (del inglés Nick's Class ) es el conjunto de problemas de resolución que se pueden resolver en tiempo polilogarítmico en una computadora paralela con un número polinomial de procesadores. En otras palabras, un problema pertenece a la clase NC si tiene constantes y puede resolverse en el tiempo usando procesadores paralelos. Stephen Cook [1] [2] lo llamó "Nick's Class" en honor a Nick Pippenger , quien realizó una extensa investigación [3] sobre circuitos con profundidad de polílogo y tamaño polinomial. [cuatro] $k$ $C$ $O(\log ^{c}n)$ ${\ estilo de visualización O (n ^ {k})}$

Así como la clase P puede considerarse como una clase de problemas maleables ( Tesis de Cobham ), NC puede considerarse como una clase de problemas que pueden resolverse eficientemente en una computadora paralela. [5] NC es un subconjunto de P porque se pueden simular cálculos polilogarítmicos paralelos mediante cálculos polinómicos secuenciales. No se sabe si NP = P es cierto, pero la mayoría de los científicos cree que no lo es, lo que implica que es probable que haya tareas maleables que son secuenciales "por naturaleza" y que no pueden acelerarse significativamente mediante el paralelismo. Así como la clase de problemas NP-completos puede considerarse como la clase de problemas "probablemente intratables", la clase de problemas P-completos , cuando se reduce a NC, puede considerarse como "probablemente no paralelizable" o "muy probablemente secuencial por naturaleza".

Una computadora paralela en la definición puede considerarse una máquina de acceso aleatorio paralelo ( PRAM - del inglés paralelo, máquina de acceso aleatorio). Es una computadora paralela con un grupo de memoria central, cualquier procesador del cual puede acceder a cualquier bit en tiempo constante. La definición de NC no se ve afectada por la forma en que PRAM accede al mismo bit desde múltiples procesadores al mismo tiempo.

NC se puede definir como el conjunto de problemas de resolución que se pueden resolver mediante un circuito booleano distribuido con profundidad polilogarítmica y un número polinomial de puertas .

Tareas en NC

NC incluye muchas tareas, incluyendo:

Suma, multiplicación y división de números enteros;
Multiplicación de matrices , contando su rango, determinante, matriz inversa ;
Polinomio mcd ;
Encontrar la coincidencia máxima.

A menudo, los algoritmos para estos problemas se idearon por separado y no podían ser una adaptación ingenua de algoritmos conocidos: el método de Gauss y el algoritmo de Euclides se basan en el hecho de que las operaciones se realizan secuencialmente.

Jerarquía NC

NC i es el conjunto de problemas de resolución que se pueden resolver mediante circuitos booleanos distribuidos con un número polinómico de compuertas (con no más de dos entradas) y profundidad , o que se pueden resolver en el tiempo mediante una computadora paralela con un número polinómico de procesadores. Obviamente, $O(\log ^{i}n)$ $O(\log ^{i}n)$

{\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots \subseteq {\mathsf {NC}}^{i}\subseteq \cdots {\ matemáticasf {NC}},

¿Qué es la jerarquía NC ?

Podemos asociar las clases NC con las clases de almacenamiento L , NL [6] y AC [7] :

{\mathsf {NC}}^{1}\subseteq {\mathsf {L}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {AC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq {\mathsf {P}}.

Las clases NC y AC se definen de forma idéntica, excepto por el número ilimitado de entradas de válvula para la clase AC. Para cada , [5] [7] es verdadero : $i$

{\mathsf {NC}}^{i}\subseteq {\mathsf {AC}}^{i}\subseteq {\mathsf {NC}}^{i+1}.

Una consecuencia de esto es NC = AC . [8] Se sabe que ambas inclusiones son estrictas para . [5] De manera similar, podemos obtener que NC es equivalente al conjunto de problemas resueltos en una máquina de Turing variable con no más de dos opciones en cada paso, y con O (log n ) memoria y alteraciones. [9] $yo=0$ ${\displaystyle (\log n)^{O(1)))$

Problema sin resolver: ¿NC es nativo?

Una de las grandes preguntas abiertas en la teoría de la complejidad computacional es si cada incorporación de la jerarquía NC es adecuada. Como señaló Papadimitriou, si NC i = NC i +1 es cierto para algunos , entonces NC i = NC j para todos y, como consecuencia, NC i = NC . Esta observación se denomina plegamiento de jerarquía NC porque incluso a partir de una sola igualdad en la cadena de anidamiento: $i$ ${\ Displaystyle j\ geqslant i}$

{\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots

se deduce que toda la jerarquía NC "colapsa" hasta cierto nivel . Por lo tanto, dos opciones son posibles: $i$

${\mathsf {NC}}^{1}\subconjunto \cdots \subconjunto {\mathsf {NC}}^{i}\subconjunto \cdots \subconjunto {\mathsf {NC}}^{i+j} \subconjunto \cdots {\mathsf {NC}}$
${\mathsf {NC}}^{1}\subconjunto \cdots \subconjunto {\mathsf {NC}}^{i}=\cdots ={\mathsf {NC}}^{i+j}=\ cdots {\mathsf {NC}}.$

Se cree ampliamente que (1) es cierto, aunque aún no se ha encontrado evidencia con respecto a la veracidad de ninguna de las declaraciones.

Teorema de Barrington

Un programa de bifurcación de ancho y largo variable consta de una secuencia de instrucciones de largo . Cada instrucción es un triple , donde es el índice de la variable a comprobar , y y son las funciones de permutación de a . Los números se llaman los estados del programa de bifurcación. El programa comienza en el estado 1, y cada instrucción cambia el estado a o , dependiendo de si la variable -ésima es igual a 0 o 1. $norte$ $k$ $metro$ $metro$ ${\ estilo de visualización (i, p, q)}$ $i$ ${\ estilo de visualización (1 \ leq i \ leq n)}$ $pags$ $q$ ${\ estilo de visualización \ {1,2,..., k\}}$ ${\ estilo de visualización \ {1,2,..., k\}}$ ${\ estilo de visualización 1,2,..., k}$ ${\ estilo de visualización (i, p, q)}$ $X$ $p(x)$ $q(x)$ $i$

La familia de programas de bifurcación consta de programas de bifurcación con variables para cada uno . $norte$ $norte$

Es fácil demostrar que cualquier lenguaje puede ser reconocido por una familia de programas de ramificación con ancho 5 y largo exponencial, o una familia con ancho exponencial y largo lineal. $L$ $\{0,1\}$

Todos los lenguajes regulares no se pueden reconocer como una familia de programas de ramificación de instrucciones lineales de ancho constante (ya que un DFA se puede convertir en un programa de ramificación). BWBP denota una clase de lenguajes reconocidos por la familia de programas de bifurcación BWBP (ancho acotado y longitud polinomial) . [10] . $\{0,1\}$

El teorema de Barrington [11] establece que BWBP es exactamente NC 1 no asignado . La demostración del teorema utiliza la indecidibilidad del grupo de simetría . [diez] ${\ estilo de visualización S_ {5}}$

Demostración del teorema de Barrington

Probemos que un programa de bifurcación ( VP ) con ancho constante y tamaño polinomial se puede convertir en un circuito de NC 1 .

Por el contrario: sea un circuito C de NC 1 . Sin pérdida de generalidad, supondremos que solo se utilizan puertas AND y NOT .

Definición: Un VI se llama -calcular una función booleana o si da como resultado - la permutación idéntica , y por su resultado - la -permutación. Dado que nuestro esquema C describe alguna función booleana y solo ella, podemos intercambiar estos términos. $\sigma$ $F$ ${\ estilo de visualización (\ sigma-f)}$ ${\ estilo de visualización f = 0}$ ${\ estilo de visualización f = 1}$ $\sigma$ $F$

Para la demostración utilizaremos dos lemas:

Lema 1 : Si hay un VP que -calcula , entonces también existe un VP que -calcula (es decir, igual a at , e igual a . $\sigma$ $F$ ${\ estilo de visualización \ sigma ^ {-1}}$ $F$ $identificación$ ${\ estilo de visualización f = 0}$ ${\ estilo de visualización \ sigma ^ {-1}}$ ${\ estilo de visualización f = 1}$

Prueba : dado que y son ciclos, y dos ciclos cualesquiera son conjugados , entonces existe una permutación tal que = . Luego multiplicamos por las permutaciones y por la primera instrucción VP de la izquierda (para obtener las permutaciones y ), y multiplicamos las permutaciones de la última instrucción por la derecha (obtenemos y ). Si antes nuestras acciones (sin pérdida de generalidad) era igual a , ahora el resultado será , y si era igual a , entonces el resultado será igual a . Entonces, tenemos un VI que calcula , con la misma longitud (el número de instrucciones no ha cambiado). $\sigma$ ${\ estilo de visualización \ sigma ^ {-1}}$ $\Pi$ ${\ estilo de visualización \ sigma ^ {-1}}$ ${\ estilo de visualización \ pi \ sigma \ pi ^ {-1}}$ $\Pi$ $p_{1}$ $q_{1}$ ${\ estilo de visualización {\ pi} p_ {1}}$ ${\ estilo de visualización {\ pi} q_ {1}}$ ${\ estilo de visualización \ pi ^ {-1}}$ ${\displaystyle p_{n}\pi^{-1))$ ${\displaystyle q_{n}\pi^{-1))$ ${p_{1}}{p_{2}}...{p_{n}}$ $identificación$ ${\pi }id{\pi }^{-1}=id$ $\sigma$ ${\ estilo de visualización \ pi \ sigma \ pi ^ {-1} = \ sigma ^ {-1}}$ ${\ estilo de visualización \ sigma ^ {-1}}$ $F$

Nota : si multiplicamos la salida de VP por la derecha, entonces de manera obvia obtenemos la función de cálculo de VP . ${\ estilo de visualización (\ sigma ^ {-1}-f)}$ $\sigma$ $\sigma$ ${\ estilo de visualización {\ neg} f}$

Lema 2 : Si hay dos VIs: -calculating y -computing con longitudes y , donde y son permutaciones de 5 ciclos, entonces existe un VI con una permutación de 5 ciclos tal que el VI -calcula y su tamaño no excede + . $\sigma$ $F$ $\gama$ $t$ $l_{1}$ $l_{2}$ $\sigma$ $\gama$ ${\displaystyle \varepsilon =\gamma \sigma \gamma ^{-1}\sigma ^{-1))$ $\varepsilon$ $f{\cuña}t$ ${\ estilo de visualización 2 (l_ {1))$ ${\ estilo de visualización l_ {2})}$

Demostración : Dispongamos "en una fila" las instrucciones de cuatro PV: , , , (construimos las inversas por el Lema 1). Si una o ambas funciones devuelven 0, entonces el resultado de un programa grande es: por ejemplo, con . Si ambas funciones devuelven 1, entonces . Aquí , lo cual es cierto debido al hecho de que estas permutaciones son 5-cíclicas (debido a la insolubilidad del grupo de simetría ). La longitud del nuevo VI se calcula por definición. ${\ estilo de visualización (\ gamma-t)}$ ${\ estilo de visualización (\ sigma-f)}$ ${\ estilo de visualización (\ gamma ^ {-1} -t)}$ ${\ estilo de visualización (\ sigma ^ {-1}-f)}$ ${\ estilo de visualización \ varepsilon = id}$ $f=0,t=1,\varepsilon =id{\sigma}id{\sigma}^{-1}=id$ ${\displaystyle \varepsilon =\gamma \sigma \gamma ^{-1}\sigma ^{-1))$ $\gamma \sigma \gamma ^{-1}\sigma ^{-1}\neq id<=>\gamma \sigma \neq \sigma \gamma$ ${\ estilo de visualización S_ {5}}$

${\ estilo de visualización}$ Prueba del teorema

Probaremos por inducción. Supongamos que tenemos un circuito C con entradas y que para todos los subcircuitos D y permutaciones de 5 ciclos hay un VI que calcula D. Demostremos que para todas las 5 permutaciones existe un VP que calcula C. $x_{1},...,x_{n}$ $\sigma$ $\sigma$ $\sigma$ $\sigma$

Si el esquema C genera , entonces el VI tiene una instrucción: verifique el valor (0 o 1) y devuelva o (respectivamente). $x_{yo}$ $x_{yo}$ $identificación$ $\sigma$
Si el circuito C produce A para algún otro circuito A , por la nota al Lema 1 creamos un VI que -calcula A. $\neg$ $\sigma$ $\neg$
Si el circuito C produce A B para los circuitos A y B , crearemos el VI deseado de acuerdo con el Lema 2. $\cuña$

El tamaño del programa de bifurcación resultante no excede , donde es la profundidad del circuito. Si el esquema tiene una profundidad logarítmica, entonces el VP tiene una longitud polinomial. ${\ estilo de visualización 4^{d))$ $d$

Notas

↑ “Hacia una teoría de la complejidad de la computación paralela sincrónica. D L'Enseignement mathematique 27” [ ing. ]. Archivado desde el original el 10 de marzo de 2022 . Consultado el 19-04-2020 . Parámetro obsoleto utilizado |deadlink=( ayuda )
↑ Cook, Stephen A. (1985-01-01). “Taxonomía de problemas con algoritmos paralelos rápidos”. Información y Control . Conferencia Internacional sobre Fundamentos de la Teoría de la Computación ]. 64 (1):2-22. DOI : 10.1016/S0019-9958(85)80041-3 . ISSN 0019-9958 .
↑ Pippenger, Nicolás (1979). “Sobre los límites de los recursos simultáneos” . 20º Simposio Anual sobre Fundamentos de Ciencias de la Computación ( SFCS 1979 ) ]: 307-311. DOI : 10.1109/SFCS.1979.29 . ISSN 0272-5428 .
↑ Arora & Barak (2009) p.120
↑ 1 2 3 Arora & Barak (2009) p.118
↑ Papadimitriou (1994) Teorema 16.1
↑ 1 2 Clote & Kranakis (2002) p.437
↑ Clote & Kranakis (2002) p.12
↑ S. Bellantoni y I. Oitavem (2004). “Separando NC a lo largo del eje delta”. Informática Teórica . 318 (1-2): 57-78. DOI : 10.1016/j.tcs.2003.10.021 .
↑ 1 2 Clote & Kranakis (2002) p.50
↑ Barrington, David A. (1989). “Los programas de bifurcación de tamaño polinomial de ancho limitado reconocen exactamente esos idiomas en NC 1 ” (PDF) . Cómputo J. sist. ciencia _ 38 (1): 150-164. DOI : 10.1016/0022-0000(89)90037-8 . ISSN 0022-0000 . Zbl 0667.68059 .

Enlaces

Arora, Sanjeev. Complejidad computacional. Un enfoque moderno / Sanjeev Arora, Boaz Barak. - Prensa de la Universidad de Cambridge , 2009. - ISBN 978-0-521-42426-4 .
Cloto, Pedro. Funciones booleanas y modelos de computación / Peter Clote, Evangelos Kranakis. - Berlín: Springer-Verlag , 2002. - ISBN 3-540-59436-1 .
Greenlaw, Raymond, James Hoover y Walter Ruzzo. Límites al cómputo en paralelo; P-Teoría de la Completitud . Archivado el 4 de junio de 2013 en Wayback Machine ISBN 0-19-508591-4
Kozen, Dexter C. El diseño y análisis de algoritmos. — 1992. Conferencias 28 — 34 y 36
Kozen, Dexter C. Teoría de la Computación. - Springer-Verlag , 2006. - ISBN 1-84628-297-7 . Lección 12: Relación deNCcon las clases de tiempo-espacio
Papadimitriou, Christos. Sección 15.3: La clase NC // Complejidad computacional . — 1er. — Addison Wesley, 1993. — P. 375–381 . — ISBN 0-201-53082-1 .
Straubing, Howard. Autómatas finitos, lógica formal y complejidad de circuitos . - Basilea: Birkhäuser, 1994. - ISBN 3-7643-3719-2 .
Vollmer, Heribert. Introducción a la complejidad del circuito. Un enfoque uniforme. - Berlín: Springer-Verlag , 1998. - ISBN 3-540-64310-9 .

Clases de complejidad de algoritmos
Considerado ligero	DLOGTIME CA 0 ACC 0 TC0 [ es L SL RL Países Bajos CAROLINA DEL NORTE SC CC PAGS P-completa ZPP PR BPP BQP EQP APX
Se supone que es difícil	UP notario público NP completo co-NP co-NP-completo AM MA QMA PH ⊕P PÁGINAS #PAGS #P- IP ESPACIO P PSPACE-completo
Considerado difícil	EXPTIME NEXPTIME EXPESPACIO 2-EXPTIM PRIMARIA R PR RE RE-completar Co-RE Co-RE-completo TODOS