NL denota la clase de idiomas, lo que puede ser decidido por una máquina de Turing determinista en uso $O(\log n)$ trabajo cinta de células.
Un lenguaje de $L$ se dice NL-duro si $\forall L' \in$ NL : $L'\leq_L L\,$ (NL-dureza)
donde $\leq_L$ denota el logaritmo de la reducción de espacio, que es también transitivo.
Dado un lenguaje L. Es la siguiente afirmación verdadera?
Reclamo: Si $\overline{L}$ es NL-duro, a continuación, $L$ también NL-duro.
Dado que el $\overline{L}$ es NL-duro, podemos espacio de registro--reducir todos los problemas contenidos en NL a $\overline{L}$, es decir, $\forall L'\in$ NL : $L'\leq_L \overline{L}$. Debido a la Immerman–Szelepcsényi teorema sabemos que coNL = NL, pero no sé si puedo hacer progresos con el hecho de que.
