Sin embargo, la complejidad del procedimiento de decisión obtenido de esta manera es normalmente mayor del que realmente se necesita; por ejemplo el problema de satisfactibilidad para la LPO con dos variables es NEXPTIME (que es una complejidad muy grande, aunque todavía es decidible) mientras que en formula_3 es PSPACE-hard (es una complejidad menor).