En otras palabras, un problema A está en P-completo si para todo problema B en P, existen constantes c y k tales que B puede ser reducido en A en tiempo O((log n)c) utilizando O(nk) procesadores paralelos.
En otras palabras, no se sabe si existen problemas resolubles que son inherentemente secuenciales.
Queda claro que el problema es P-completo: Si se pudiera paralelizar una simulación general de una máquina secuencial, se tendría un método general para paralelizar cualquier programa que corre en esa máquina.
El interés no está realmente en saber si un problema se puede resolver rápidamente en una máquina paralela.
En cambio, si T está escrito como un número unario (una cadena de n unos, para n=T), solo toma tiempo n. Al escribir T en unario en lugar de binario, se reduce el algoritmo obviamente secuencial de tiempo exponencial a lineal, lo cual coloca el problema en la categoría P. Por tanto estará en NC si y solo si es paralelizable.