NC (complejidad)

Problema no resuelto en informática :

⁠ ⁠ ${\displaystyle {\mathsf {NC}}{\overset {?}{=}}{\mathsf {P}}}$

(más problemas sin resolver en informática)

En teoría de la complejidad computacional , la clase NC (por "Nick's Class") 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 con tamaño de entrada n está en NC si existen constantes c y k tales que pueda resolverse en el tiempo O ((log n ) ^c ) usando procesadores paralelos O ( n ^k ) . Stephen Cook ^{[1] [2]} acuñó el nombre "clase de Nick" en honor a Nick Pippenger , quien había realizado una extensa investigación ^[3] sobre circuitos con profundidad polilogarítmica y tamaño polinomial. ^[4]

Así como la clase P puede considerarse como los problemas manejables ( tesis de Cobham ), los NC pueden considerarse como los problemas que pueden resolverse eficientemente en una computadora paralela. ^[5] NC es un subconjunto de P porque los cálculos paralelos polilogarítmicos pueden simularse mediante cálculos secuenciales de tiempo polinomial. 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 tratables que son "intrínsecamente secuenciales" y no pueden acelerarse significativamente mediante el uso del paralelismo. Así como la clase NP-completa puede considerarse "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 ). Se trata de una computadora paralela con un conjunto 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 la PRAM maneja el acceso simultáneo a un solo bit por parte de 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 decidibles 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ítmico. profundidad y un número polinómico de puertas con un abanico máximo de 2.

RNC es una clase que extiende NC con acceso a la aleatoriedad.

Problemas en Carolina del Norte

Al igual que con P , mediante un ligero abuso del lenguaje, se podrían clasificar los problemas de función y los problemas de búsqueda como NC . Se sabe que NC incluye muchos problemas, incluidos

• Suma, multiplicación y división de números enteros;
• Multiplicación de matrices , determinante, inversa , rango;
• MCD polinómico, mediante reducción a álgebra lineal utilizando la matriz de Sylvester
• Encontrar una coincidencia máxima.

A menudo, los algoritmos para esos problemas tuvieron que inventarse por separado y no pudieron adaptarse ingenuamente a partir de algoritmos conocidos: la eliminación gaussiana y el algoritmo euclidiano se basan en operaciones realizadas en secuencia. Se podría contrastar el sumador de acarreo de ondulación con un sumador de acarreo anticipado .

Ejemplo

Un ejemplo de problema en NC ¹ es la verificación de paridad en una cadena de bits. ^[6] El problema consiste en contar el número de unos en una cadena formada por 1 y 0. Una solución sencilla consiste en sumar todos los bits de la cadena. Como la suma es asociativa, . Aplicando recursivamente dicha propiedad, es posible construir un árbol binario de longitud en el que cada suma entre dos bits y sea expresable mediante operadores lógicos básicos , por ejemplo, mediante la expresión booleana . ${\displaystyle x_{1}+\cdots +x_{n}=(x_{1}+\cdots +x_{\frac {n}{2}})+(x_{{\frac {n}{2}}+1}+\cdots +x_{n})}$ ${\displaystyle O(log(n))}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle (x_{i}\land \neg x_{j})\lor (\neg x_{i}\land x_{j})}$

La jerarquía NC

NC ⁱ es la clase de problemas de decisión decidibles mediante circuitos booleanos uniformes con un número polinómico de puertas de como máximo dos entradas y profundidad O ((log n ) ⁱ ) , o la clase de problemas de decisión resolubles en el tiempo O ((log n ) ⁱ ) en una computadora paralela con un número polinómico de procesadores. Claramente, tenemos

${\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots \subseteq {\mathsf {NC}}^{i}\subseteq \cdots {\mathsf {NC}}}$

que forma la jerarquía NC .

Podemos relacionar las clases NC con las clases espaciales L y NL ^[7] y AC . ^[8]

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

Las clases NC están relacionadas con las clases AC, que se definen de manera similar, pero con puertas que tienen una entrada en abanico ilimitada. Para cada i , tenemos ^{[5] [8]}

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

Como consecuencia inmediata de esto, tenemos que NC = AC . ^[9] Se sabe que ambas inclusiones son estrictas para i = 0. ^[5]

De manera similar, tenemos que NC es equivalente a los problemas solucionables en una máquina de Turing alterna restringida a como máximo dos opciones en cada paso con espacio O (log n ) y alternancias. ^[10] ${\displaystyle (\log n)^{O(1)}}$

Problema abierto: ¿NC es correcto?

Una importante pregunta abierta en la teoría de la complejidad es si cada contención en la jerarquía NC es adecuada o no . Papadimitriou observó que, si NC ⁱ = NC ^{i +1} para algunos i , entonces NC ⁱ = NC ^j para todos los j  ≥  i , y como resultado, NC ⁱ = NC . Esta observación se conoce como colapso de jerarquía NC porque incluso una sola igualdad en la cadena de contenciones

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

implica que toda la jerarquía NC "colapsa" hasta algún nivel i . Así, existen 2 posibilidades:

1. ${\displaystyle {\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}\subset \cdots \subset {\mathsf {NC}}^{i+j}\subset \cdots {\mathsf {NC}}}$
2. ${\displaystyle {\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}=\cdots ={\mathsf {NC}}^{i+j}=\cdots {\mathsf {NC}}}$

Se cree ampliamente que (1) es así, aunque aún no se ha descubierto ninguna prueba de la veracidad de ninguna de las afirmaciones.

CAROLINA DEL NORTE0

La clase especial NC ⁰ sólo funciona 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 de entrada acotado.

teorema de barrington

Un programa ramificado 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 a verificar (1 ≤ i ≤ n ), y p y q son funciones de {1, 2, ..., k } a {1, 2, ..., k }. Los números 1, 2, ..., k se denominan estados del programa de ramificación. El programa comienza inicialmente 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 la i -ésima variable es 0 o 1. La función que asigna un entrada a un estado final del programa se llama rendimiento del programa (más precisamente, el rendimiento de una entrada es la función que asigna cualquier estado inicial al estado final correspondiente). El programa acepta un conjunto de valores de variables cuando hay algún conjunto de funciones tales que una secuencia de variables está en A precisamente cuando su rendimiento está en F. ${\displaystyle A\subset 2^{n}}$ ${\displaystyle F\subset k^{k}}$ ${\displaystyle x\in 2^{n}}$

Una familia de programas de ramificación consta de un programa de ramificación con n variables para cada n . Acepta un idioma cuando el programa de n variables acepta el idioma restringido a una longitud de n entradas.

Es fácil demostrar que cada lenguaje L en {0,1} puede ser reconocido por una familia de programas ramificados de ancho 5 y largo exponencial, o por una familia de ancho exponencial y largo lineal.

Cada lenguaje normal en {0,1} puede ser reconocido por una familia de programas ramificados de ancho constante y número lineal de instrucciones (ya que un DFA se puede convertir en un programa ramificado). BWBP denota la clase de lenguajes reconocibles por una familia de programas ramificados de ancho acotado y longitud polinomial. ^[11]

El teorema de Barrington ^[12] dice que BWBP es exactamente NC ¹ no uniforme . La prueba utiliza la no solubilidad del grupo simétrico S ₅ . ^[11]

El teorema es bastante sorprendente. Por ejemplo, implica que la función mayoritaria puede calcularse mediante una familia de programas ramificados de ancho y tamaño polinómico constantes, mientras que la intuición podría sugerir que para lograr un tamaño polinómico se necesita un número lineal de estados.

Prueba del teorema de Barrington

Un programa de ramificación de ancho constante y tamaño polinómico se puede convertir fácilmente (mediante divide y vencerás) en un circuito en NC ¹ .

Por el contrario, supongamos que se da un circuito en NC ¹ . Sin pérdida de generalidad, supongamos que utiliza sólo puertas AND y NOT.

Lema 1  :  si existe un programa de ramificación que a veces funciona como una permutación P y a veces como una permutación Q , multiplicando las permutaciones por la derecha en la primera instrucción por α y en la última instrucción multiplicando por la izquierda por β , podemos hacer un circuito de la misma longitud que se comporta como β P α o β Q α , respectivamente.

Llame a un programa de ramificación α para calcular 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 de 5 α , β , si existe un programa de bifurcación α que calcula un circuito C , entonces existe un programa de bifurcación β que calcula el circuito C , de la misma longitud.

Lema 2  :  existen 5 ciclos γ , δ tales que su conmutador ε = γδγ ⁻¹ δ ⁻¹ es un ciclo de 5. Por ejemplo, γ = (1 2 3 4 5), δ = (1 3 5 4 2) dando ε = (1 3 2 5 4).

Prueba

Ahora demostraremos el teorema de Barrington por inducción:

Supongamos que tenemos un circuito C que toma entradas x ₁ ,..., x _n y supongamos que para todos los subcircuitos D de C y 5 ciclos α, existe un programa ramificado de computación α D. Demostraremos que para todos los 5 ciclos α, existe un programa ramificado de computación α C.

• Si el circuito C simplemente genera algún bit de entrada x _i , el programa de ramificación que necesitamos tiene solo una instrucción: verificar el valor de x _i (0 o 1) y generar la identidad o α (respectivamente).
• Si el circuito C genera ¬ A para algún circuito A diferente , cree un programa de ramificación α ⁻¹ -calcule A y luego multiplique la salida del programa por α. Por el Lema 1, obtenemos un programa ramificado para A que genera la identidad o α, es decir, α -calcula ¬ A = C.
• Si el circuito C genera A ∧ B para los circuitos A y B , únase a los programas de bifurcación que γ -calcula A , δ -calcula B , γ ⁻¹ -calcula A y δ ⁻¹ -calcula B para elegir entre 5 ciclos. γ y δ tales que su conmutador ε = γδγ ⁻¹ δ ⁻¹ también es de 5 ciclos. (La existencia de tales elementos se estableció en el Lema 2.) Si uno o ambos circuitos generan 0, el programa resultante será la identidad debido a la cancelación; Si ambos circuitos generan 1, el programa resultante generará el conmutador ε . En otras palabras, obtenemos un programa ε que calcula A ∧ B. Debido a que ε y α son dos ciclos de 5, son conjugados y, por lo tanto, existe un programa α que calcula A ∧ B según el Lema 1.

Al suponer que los subcircuitos tienen programas de ramificación de modo que α -calculan para todos los 5 ciclos α ∈ S ₅ , hemos demostrado que C también tiene esta propiedad, según sea necesario.

El tamaño del programa de bifurcació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 polinómica.

Notas

1. Cocinero, SA (1981). "Hacia una teoría de la complejidad de la computación paralela síncrona". L'Enseignement Mathématique . 27 : 99-124. Archivado desde el original el 10 de marzo de 2022.
2. Cocinero, Stephen A. (1 de enero de 1985). "Una taxonomía de problemas con algoritmos paralelos rápidos". 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.
3. Pippenger, Nicolás (1979). "Sobre límites simultáneos de recursos". Vigésimo Simposio Anual sobre Fundamentos de la Informática (SFCS 1979) : 307–311. doi :10.1109/SFCS.1979.29. ISSN  0272-5428. S2CID  7029313.
4. Arora y Barak (2009) p.120
5. Arora y Barak (2009) p.118
6. David mezcla Barrington; Alexis Maciel (18-07-2000). "Conferencia 2: La complejidad de algunos problemas" (PDF) . Sesión de verano 2000 de IAS/PCMI - Programa de pregrado en Matemáticas Clay - Curso básico sobre complejidad computacional . Universidad Clarkson . Consultado el 11 de noviembre de 2021 .
7. Papadimitriou (1994) Teorema 16.1
8. Clote y Kranakis (2002) p.437
9. Clote y Kranakis (2002) p.12
10. S. Bellantoni e 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.
11. Clote y Kranakis (2002) p.50
12. Barrington, David A. (1989). "Los programas de ramificación de tamaño polinómico de ancho limitado reconocen exactamente esos idiomas en NC1" (PDF) . J. Computación. Sistema. Ciencia . 38 (1): 150–164. doi : 10.1016/0022-0000(89)90037-8 . ISSN  0022-0000. Zbl  0667.68059.

Referencias

• Arora, Sanjeev ; Barac, Booz (2009). Complejidad computacional. Un enfoque moderno . Prensa de la Universidad de Cambridge . ISBN 978-0-521-42426-4. Zbl  1193.68112.
• Clote, Pedro; Kranakis, Evangelos (2002). Funciones booleanas y modelos de cálculo . Textos de 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 del cálculo paralelo; P-Teoría de la integridad. 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.Conferencia 12: Relación de NC con las clases espacio-temporales
• Papadimitriou, Christos (1993). "Artículo 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 . Avances 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 de Informática Teórica. Berlín: Springer-Verlag . ISBN 3-540-64310-9. Zbl  0931.68055.