Supongamos que L = P. Deje que A sea un problema en NP. Según la definición del verificador de NP, cada solución positiva a A tiene un testigo que puede verificarse en tiempo polinómico. Como P = L, la misma solución se puede verificar en el espacio logarítmico. Así NP = NL.
No has demostrado que NP=NL . El único método que has derivado para mostrar quex ∈ A, es no adivinar "adivinar" un testigo yy use el algoritmo determinista de espacio de registro para verificarlo. Sin embargo,yen sí mismo puede ser polinómicamente largo, mientras que su máquina NL solo puede adivinar logarítmicamente muchos bits: su máquina NL no tiene suficiente espacio para almacenar el testigo, por lo que no tiene un algoritmo NL .
Además, nota que ya sabemos que los testigos de NP problemas -Complete puede ser verificada en una clase de complejidad menor que L . El teorema de Fagin dice que NP es exactamente el conjunto de problemas que se pueden definir en el fragmento existencial de la lógica de segundo orden. Esto es equivalente a decir que puede verificar un testigo de longitud polinómica usando lógica de primer orden. FO es estrictamente más débil que L , ya que la lógica de primer orden no puede resolver problemas simples de espacio de registro como decirle si su cadena testigo contiene un número par de 1s.