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.