NC (clase de complejidad)

En teoría de la complejidad computacional, la clase de complejidad NC (la clase de Nick) es el conjunto de los problemas de decisión que pueden ser resueltos mediante computación paralela con un número polinómico de procesadores en tiempo polilogarítmico. Dicho de otra forma, un problema está en NC si existen constantes c y k tales que el problema puede ser resuelto en tiempo O((log n)^c) utilizando O(n^k) procesadores paralelos.

Al igual que los problemas de P pueden verse como los problemas resolubles en una máquina secuencial, los de NC pueden verse como aquellos que pueden resolverse eficientemente en una máquina paralela. NC es subconjunto de P dado que las máquinas paralelas pueden simularse con máquinas secuenciales. No se ha determinado si NC = P, pero se piensa que son clases diferentes, lo que querría decir que algunos problemas no pueden ser mejorados usando una máquina paralela. Al igual que la clase NP-completo puede verse como la clase de problemas "seguramente sin solución eficiente", la clase P-completo puede verse como la clase de problemas "seguramente no paralelizables".

Stephen Cook acuñó el término NC (Clase de Nick) en honor a Nick Pippenger, quien ha investigado los circuitos de profundidad polilogarítmica y tamaño polinómico.

Referencias

• Greenlaw, Raymond, James Hoover, and Walter Ruzzo. Limits To Parallel computation; P-Completeness Theory. ISBN 0-19-508591-4

• Datos: Q1141840