NC (complejidad)
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 considerarse "probablemente intratable", la claseP-complete , cuando se utilizanreducciones NC , se puede considerar 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.
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