NC (complejidad)

Problema sin resolver en informática :

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

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

En teoría de 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 se puede resolver en tiempo O ((log n ) ^c ) usando O ( n ^k ) procesadores paralelos. 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 tratables ( tesis de Cobham ), NC puede 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 haya algunos problemas tratables que sean "inherentemente secuenciales" y no se puedan acelerar significativamente mediante el uso del paralelismo. Así como la clase NP-completa puede considerarse 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 de la definición es una máquina de acceso aleatorio paralela ( PRAM ). Es decir, 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 puede definirse como aquellos problemas de decisión decidibles por un circuito booleano uniforme (que puede calcularse 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 profundidad polilogarítmica y un número polinomial de puertas con un fan-in 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 pertenecientes a NC . Se sabe que NC incluye muchos problemas, entre ellos

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

A menudo, los algoritmos para esos problemas debían inventarse por separado y no podían adaptarse de manera ingenua a partir 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 de ondulación con un sumador de acarreo anticipado .

Ejemplo

Un ejemplo de problema en NC ¹ es la comprobación de paridad en una cadena de bits. ^[6] El problema consiste en contar el número de 1 en una cadena formada por 1 y 0. Una solución sencilla consiste en sumar todos los bits de la cadena. Como la adición 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 por medio de 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 por circuitos booleanos uniformes con un número polinomial de puertas de como máximo dos entradas y profundidad O ((log n ) ⁱ ) , o la clase de problemas de decisión resolubles en tiempo O ((log n ) ⁱ ) en una computadora paralela con un número polinomial 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 un abanico de entrada ilimitado. 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 resolubles en una máquina de Turing alterna restringida a un máximo de dos opciones en cada paso con espacio O (log n ) y alternancias. ^[10] ${\displaystyle (\log n)^{O(1)}}$

Problema abierto: ¿Es correcto NC?

Una de las principales preguntas abiertas en la teoría de la complejidad es si cada contención en la jerarquía NC es apropiada o no. Papadimitriou observó que, si NC ⁱ = NC ^{i +1} para algún i , entonces NC ⁱ = NC ^j para todo j  ≥  i , y como resultado, NC ⁱ = NC . Esta observación se conoce como colapso de la 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 "se derrumba" hasta un cierto nivel i . Por lo tanto, hay dos 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 el caso, aunque todavía no se ha descubierto ninguna prueba de la verdad de ninguna de las afirmaciones.

CAROLINA DEL NORTE0

La clase especial NC ⁰ opera únicamente con una longitud constante de bits de entrada. Por lo tanto, se la describe como la clase de funciones definibles por circuitos booleanos uniformes con profundidad constante y entrada en abanico limitada.

Teorema de Barrington

Un programa de ramificación con n variables de ancho k y longitud 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 comprobar (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 una entrada a un estado final del programa se denomina 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 variables cuando existe un conjunto de funciones tales que una secuencia variable está en A precisamente cuando su resultado está en F. ${\displaystyle A\subset 2^{n}}$ ${\displaystyle F\subset k^{k}}$ ${\displaystyle x\in 2^{n}}$

Una familia de programas ramificados consta de un programa ramificado con n variables para cada n . Acepta un lenguaje cuando el programa con n variables acepta el lenguaje restringido a entradas de longitud n .

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

Todo lenguaje regular 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 puede convertirse en un programa de ramificación). BWBP denota la clase de lenguajes reconocibles por una familia de programas de ramificación de ancho limitado y longitud polinómica. ^[11]

El teorema de Barrington ^[12] dice que BWBP es exactamente no uniforme NC ¹ . 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 constante y tamaño polinómico, 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 polinomial se puede convertir fácilmente (mediante dividir y vencer) en un circuito en NC ¹ .

Por el contrario, supongamos que se da un circuito en NC ^1. Sin pérdida de generalidad, supongamos que utiliza solo 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 , al multiplicar por la derecha las permutaciones en la primera instrucción por α , y en la última instrucción por la izquierda por β , podemos hacer un circuito de la misma longitud que se comporta como β P α o β Q α , respectivamente.

Llamemos a un programa de ramificación que calcula α 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 cualesquiera dos 5-ciclos α , β , si existe un programa de ramificación α-que calcula un circuito C , entonces existe un programa de ramificació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 asumimos que para todos los subcircuitos D de C y 5-ciclos α, existe un programa de ramificación α-computando D . Demostraremos que para todos los 5-ciclos α, existe un programa de ramificación α-computando C .

• Si el circuito C simplemente genera un 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 un circuito diferente A , creamos un programa de ramificación que calcule α ⁻¹ A y luego multiplicamos la salida del programa por α. Por el Lema 1, obtenemos un programa de ramificación 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 , se unen los programas de ramificación que γ -calculan A , δ -calculan B , γ ⁻¹ -calculan A y δ ⁻¹ -calculan B para una elección de 5-ciclos γ y δ tales que su conmutador ε = γδγ ⁻¹ δ ⁻¹ también es un 5-ciclo. (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 . Como ε y α son dos 5-ciclos, son conjugados y, por lo tanto, existe un programa α que calcula A ∧ B mediante el Lema 1.

Al suponer que los subcircuitos tienen programas de ramificación de modo que son α- computadores para todos los 5 ciclos α ∈ S ₅ , hemos demostrado que C también tiene esta propiedad, como se requiere.

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 una profundidad logarítmica, el programa de ramificación tiene una longitud polinómica.

Notas

1. Cook, SA (1981). "Hacia una teoría de la complejidad de la computación paralela sincrónica". L'Enseignement Mathématique . 27 : 99–124. Archivado desde el original el 10 de marzo de 2022.
2. Cook, Stephen A. (1 de enero de 1985). "Una 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.
3. Pippenger, Nicholas (1979). "Sobre límites simultáneos de recursos". 20.º Simposio Anual sobre Fundamentos de la Ciencia de la Computación (SFCS 1979) : 307–311. doi :10.1109/SFCS.1979.29. ISSN  0272-5428. S2CID  7029313.
4. Arora y Barak (2009) pág. 120
5. Arora y Barak (2009) p.118
6. David Mix Barrington; Alexis Maciel (18 de julio de 2000). "Conferencia 2: La complejidad de algunos problemas" (PDF) . Sesión de verano 2000 de la IAS/PCMI - Programa de pregrado de matemáticas de Clay - Curso básico sobre complejidad computacional . Universidad de Clarkson . Consultado el 11 de noviembre de 2021 .
7. Papadimitriou (1994) Teorema 16.1
8. Clote y Kranakis (2002) pág. 437
9. Clote y Kranakis (2002) pág. 12
10. S. Bellantoni y I. Oitavem (2004). "Separación de NC a lo largo del eje delta". Ciencias Informáticas Teóricas . 318 (1–2): 57–78. doi :10.1016/j.tcs.2003.10.021.
11. Clote y Kranakis (2002) pág. 50
12. Barrington, David A. (1989). "Los programas de ramificación de tamaño polinomial de ancho limitado reconocen exactamente esos lenguajes en NC1" (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 . Cambridge University Press . ISBN 978-0-521-42426-4.Zbl 1193.68112  .
• Clote, Peter; Kranakis, Evangelos (2002). Funciones booleanas y modelos computacionales . Textos en informática teórica. Serie EATCS. ​​Berlín: Springer-Verlag . ISBN. 3-540-59436-1.Zbl 1016.94046  .
• Greenlaw, Raymond, James Hoover y Walter Ruzzo. Límites de la computación paralela; teoría de la p-completitud. ISBN 0-19-508591-4 
• Kozen, Dexter C. (1992). El diseño y análisis de algoritmos .Lecciones 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  .Lección 12: Relación de NC con las clases de tiempo y espacio
• Papadimitriou, Christos (1993). "Sección 15.3: La clase NC ". Complejidad computacional (1.ª ed.). Addison Wesley. pp. 375–381. ISBN 0-201-53082-1.
• Straubing, Howard (1994). Autómatas finitos, lógica formal y complejidad de circuitos . Progreso en la ciencia informática teórica. Basilea: Birkhäuser. ISBN 3-7643-3719-2.Zbl 0816.68086  .
• Vollmer, Heribert (1998). Introducción a la complejidad de circuitos. Un enfoque uniforme. Textos en informática teórica. Berlín: Springer-Verlag . ISBN 3-540-64310-9.Zbl 0931.68055  .