NC (clase de complejidad)

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(nk) 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.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.