En la teoría de la complejidad computacional , la clase NC (para "Clase de Nick") es el conjunto de problemas de decisión decidibles en tiempo polilogarítmico en una computadora paralela con un número polinomial de procesadores. En otras palabras, un problema es en NC si existen constantes c y k tal que puede ser resuelto en el tiempo O (log c n ) utilizando O ( n k ) procesadores paralelos. Stephen Cook [1] [2] acuñó el nombre de "la clase de Nick" en honor a Nick Pippenger., que había realizado una extensa investigación [3] sobre circuitos con profundidad polilogarítmica y tamaño polinomial. [4]
Así como se puede pensar en la clase P como los problemas tratables ( tesis de Cobham ), también se puede pensar en NC como los problemas que pueden resolverse eficientemente en una computadora paralela. [5] NC es un subconjunto de P porque los cálculos polilogarítmicos paralelos pueden ser simulados por polinomios secuenciales en tiempo. Se desconoce si NC = P , pero la mayoría de los investigadores sospechan que esto es falso, lo que significa que probablemente hay algunos problemas manejables que son "inherentemente secuenciales" y no pueden acelerarse significativamente mediante el uso del paralelismo. Así como la clase NP-completa puede pensarse como "probablemente intratable", la clase P-completa , cuando se utilizan reducciones NC , puede considerarse como "probablemente no paralelizable" o "probablemente inherentemente secuencial".
Se puede suponer que la computadora paralela en la definición es una máquina paralela de acceso aleatorio ( PRAM ). Es una computadora paralela con un grupo central de memoria, y cualquier procesador puede acceder a cualquier bit de memoria en tiempo constante. La definición de NC no se ve afectada por la elección de cómo el PRAM maneja el acceso simultáneo a un solo bit por más de un procesador. Puede ser CRCW, CREW o EREW. Consulte PRAM para obtener descripciones de esos modelos.
De manera equivalente, NC se puede definir como aquellos problemas de decisión que se pueden decidir por un circuito booleano uniforme (que se puede calcular a partir de la longitud de la entrada, para NC, suponemos que podemos calcular el circuito booleano de tamaño n en el espacio logarítmico en n ) con polilogarítmica profundidad y un número polinomial de puertas con un abanico máximo de 2.
RNC es una clase que extiende NC con acceso a la aleatoriedad.
Problemas en NC
Al igual que con P , mediante un ligero abuso de lenguaje, se podrían clasificar los problemas de función y los problemas de búsqueda como en NC . Se sabe que NC incluye muchos problemas, incluidos
- Suma, multiplicación y división de enteros;
- Multiplicación de matrices , determinante, inversa , rango;
- Polinomio GCD, mediante una reducción a álgebra lineal utilizando la matriz de Sylvester
- Encontrar una coincidencia máxima.
A menudo, los algoritmos para esos problemas tenían que inventarse por separado y no podían adaptarse ingenuamente de algoritmos bien conocidos: la eliminación gaussiana y el algoritmo euclidiano se basan en operaciones realizadas en secuencia. Se podría contrastar el sumador de acarreo ondulado con un sumador de acarreo anticipado .
La jerarquía NC
NC i es la clase de problemas de decisión que se pueden decidir por circuitos booleanos uniformes con un número polinomial de puertas de como máximo dos entradas y profundidad O (log i n ) , o la clase de problemas de decisión que se pueden resolver en el tiempo O (log i n ) en un Computadora en paralelo con un número polinomio de procesadores. Claramente, tenemos
que forma la jerarquía NC .
Podemos relacionar las clases NC con las clases espaciales L y NL [6] y AC . [7]
Las clases NC están relacionadas con las clases AC, que se definen de manera similar, pero con puertas que tienen un abanico ilimitado. Para cada i , tenemos [5] [7]
Como consecuencia inmediata de esto, tenemos que NC = AC . [8] Se sabe que ambas inclusiones son estrictas para i = 0. [5]
De manera similar, tenemos que NC es equivalente a los problemas que se pueden resolver en una máquina de Turing alterna restringida a un máximo de dos opciones en cada paso con espacio O (log n ) yalternancias. [9]
Problema abierto: ¿NC es adecuado?
Una gran cuestión abierta en la teoría de la complejidad es si todas las contención en la jerarquía de CN son adecuadas o no . Papadimitriou observó que, si NC i = NC i +1 para algún i , entonces NC i = NC j para todo j ≥ i , y como resultado, NC i = NC . Esta observación se conoce como colapso de la jerarquía NC porque incluso una sola igualdad en la cadena de contención
implica que toda la jerarquía de NC "colapsa" hasta algún nivel i . Por tanto, existen 2 posibilidades:
Se cree ampliamente que (1) es el caso, aunque aún no se ha descubierto ninguna prueba de la veracidad de ninguna de las dos afirmaciones.
NC 0
La clase especial NC 0 opera solo con una longitud constante de bits de entrada. Por lo tanto, se describe como la clase de funciones definibles por circuitos booleanos uniformes con profundidad constante y abanico acotado.
Teorema de Barrington
Un programa de ramificación con n variables de ancho k y largo m consta de una secuencia de m instrucciones. Cada una de las instrucciones es una tupla ( i , p , q ), donde i es el índice de la variable para comprobar (1 ≤ i ≤ n ), y p y q son funciones de {1, 2, ..., k } para {1, 2, ..., k }. Los números 1, 2, ..., k se denominan estados del programa de ramificación. El programa inicialmente comienza en el estado 1, y cada instrucción ( i , p , q ) cambia el estado de x a p ( x ) o q ( x ), dependiendo de si el i ésimo variable es 0 o 1.
Una familia de programas de ramificación consta de un programa de ramificación con n variables para cada n .
Es fácil mostrar que cada lenguaje L en {0,1} puede ser reconocido por una familia de programas de ramificación de ancho 5 y largo exponencial, o por una familia de ancho exponencial y largo lineal.
Cada idioma normal en {0,1} puede ser reconocido por una familia de programas de ramificación de ancho constante y número lineal de instrucciones (ya que un DFA se puede convertir en un programa de ramificación). BWBP denota la clase de lenguajes reconocibles por una familia de programas de ramificación de ancho acotado y longitud polinomial. [10]
El teorema de Barrington [11] dice que BWBP es exactamente NC 1 no uniforme . La demostración utiliza la no solubilidad del grupo simétrico S 5 . [10]
El teorema es bastante sorprendente. Por ejemplo, implica que la función mayoritaria puede ser calculada por una familia de programas de ramificación de ancho constante y tamaño polinomial, mientras que la intuición podría sugerir que para lograr un tamaño polinomial, se necesita un número lineal de estados.
Prueba del teorema de Barrington
Un programa de ramificación de ancho constante y tamaño de polinomio se puede convertir fácilmente (a través de dividir y conquistar) en un circuito en NC 1 .
A la inversa, suponga que se da un circuito en NC 1 . Sin pérdida de generalidad, suponga que usa solo puertas Y y NO.
Lema 1: Si existe un programa de ramificación que a veces funciona como una permutación P y otras como una permutación Q , multiplicando por la derecha las permutaciones en la primera instrucción por α, y en la última instrucción por la izquierda multiplicando por β, podemos hacer un circuito de la misma longitud que se comporta como β P α o β Q α, respectivamente.
Llame a un programa de ramificación α-computación un circuito C si funciona como identidad cuando la salida de C es 0, y como α cuando la salida de C es 1.
Como consecuencia del Lema 1 y del hecho de que todos los ciclos de longitud 5 son conjugados , para dos ciclos cualesquiera α, β, si existe un programa de ramificación α-computando un circuito C , entonces existe un programa de ramificación β-computación el circuito C , de la misma longitud.
Lema 2: Existen 5 ciclos γ, δ tales que su conmutador ε = γδγ −1 δ −1 es un 5 ciclos. Por ejemplo, γ = (1 2 3 4 5), δ = (1 3 5 4 2) dando ε = (1 3 2 5 4).
Ahora probaremos el teorema de Barrington por inducción:
Supongamos que tenemos un circuito de C que tiene entradas x 1 , ..., x n y asumir que para todos los subcircuitos D de C y 5 ciclos alpha, existe un programa de ramificación α-computing D . Vamos a demostrar que para todos los ciclos de 5-alfa, existe un programa de computación ramificación α- C .
- Si el circuito C emite simplemente algunos bits de entrada x i , el programa de ramificación que necesitamos tiene una sola instrucción: la comprobación x i ' s valor (0 ó 1), y la salida de la identidad o α (respectivamente).
- Si el circuito C emite ¬ A para algún circuito A diferente , cree un programa de ramificación α −1 -calcule A y luego multiplique la salida del programa por α. Por el Lema 1, obtenemos un programa de ramificación para A la salida de la identidad o α, es decir, α-computing ¬ A = C .
- Si el circuito C salidas A ∧ B para los circuitos A y B , se unen a los programas de ramificación que γ-compute A , δ-compute B, γ -1 -compute A , y δ -1 B -compute para una selección de 5 ciclos γ y δ tales que su conmutador ε = γδγ −1 δ −1 también es un ciclo de 5. (La existencia de tales elementos se estableció en el Lema 2.) Si uno o ambos circuitos dan salida a 0, el programa resultante será la identidad debido a la cancelación; si ambos circuitos emiten 1, el programa resultante emitirá el conmutador ε. En otras palabras, tenemos un programa de computación ε- A ∧ B . Debido a que ε y α son dos ciclos de 5, son conjugados y, por lo tanto, existe un programa que calcula α A ∧ B por el Lema 1.
Suponiendo que los subcircuitos tienen programas de ramificación de modo que sean α-computación para todos los 5 ciclos α∈ S 5 , hemos demostrado que C también tiene esta propiedad, según se requiera.
El tamaño del programa de ramificación es como máximo 4 d , donde d es la profundidad del circuito. Si el circuito tiene profundidad logarítmica, el programa de ramificación tiene longitud polinomial.
Notas
- ^ "Hacia una teoría de la complejidad de la computación paralela sincrónica. D L'Enseignement mathique 27" . Cite journal requiere
|journal=
( ayuda ) - ^ Cook, Stephen A. (1 de enero de 1985). "Una taxonomía de problemas con algoritmos rápidos en paralelo" . Información y control . Congreso 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, Nicholas (1979). "Sobre límites de recursos simultáneos" . 20º Simposio anual sobre los fundamentos de la informática (SFCS 1979) : 307–311. doi : 10.1109 / SFCS.1979.29 . ISSN 0272-5428 .
- ^ Arora y Barak (2009) p.120
- ↑ a b c Arora y Barak (2009) p.118
- ^ Teorema 16.1 de Papadimitriou (1994)
- ↑ a b Clote y Kranakis (2002) p.437
- ^ Clote y Kranakis (2002) p.12
- ^ S. Bellantoni e I. Oitavem (2004). "Separación NC a lo largo del eje delta". Informática Teórica . 318 (1–2): 57–78. doi : 10.1016 / j.tcs.2003.10.021 .
- ↑ a b Clote y Kranakis (2002) p.50
- ^ Barrington, David A. (1989). "Los programas de ramificación de tamaño polinómico de ancho acotado reconocen exactamente esos idiomas en NC 1 " (PDF) . J. Comput. Syst. Sci . 38 (1): 150-164. doi : 10.1016 / 0022-0000 (89) 90037-8 . ISSN 0022-0000 . Zbl 0667.68059 .
Referencias
- Arora, Sanjeev ; Barak, Boaz (2009). Complejidad computacional. Un enfoque moderno . Prensa de la Universidad de Cambridge . ISBN 978-0-521-42426-4. Zbl 1193.68112 .
- Clote, Peter; Kranakis, Evangelos (2002). Funciones booleanas y modelos de cálculo . Textos en Informática Teórica. Una serie EATCS. Berlín: Springer-Verlag . ISBN 3-540-59436-1. Zbl 1016.94046 .
- Greenlaw, Raymond, James Hoover y Walter Ruzzo. Límites al cálculo paralelo; Teoría P-Completitud .ISBN 0-19-508591-4
- Kozen, Dexter C. (1992). El diseño y análisis de algoritmos . Conferencias 28 - 34 y 36
- Kozen, Dexter C. (2006). Teoría de la Computación . Textos en Informática. Springer-Verlag . ISBN 1-84628-297-7. Zbl 1102.68025 .Clase 12: Relación de NC con las clases espacio-temporales
- Papadimitriou, Christos (1993). "Sección 15.3: La clase NC ". Complejidad computacional (1ª ed.). Addison Wesley. págs. 375–381. ISBN 0-201-53082-1.
- Straubing, Howard (1994). Autómatas finitos, lógica formal y complejidad de circuitos . Progreso en Informática Teórica. Basilea: Birkhäuser. ISBN 3-7643-3719-2. Zbl 0816.68086 .
- Vollmer, Heribert (1998). Introducción a la complejidad de los circuitos. Un enfoque uniforme . Textos en Informática Teórica. Berlín: Springer-Verlag . ISBN 3-540-64310-9. Zbl 0931.68055 .