La clase NP-completo, que puede verse como la que contiene los problemas que probablemente no son resolubles eficientemente, fue introducida para analizar el problema P=NP, y la clase P-completo, que contiene los problemas "probablemente no paralelizables" o "probablemente inherentemente secuenciales" se utiliza igualmente para estudiar la pregunta NC=P.