Paridade-L vs. NL

13

Paridade-L, também conhecida como L, é o conjunto de idiomas reconhecidos por uma máquina de Turing não determinística que só pode distinguir entre um número par ou um número ímpar de caminhos de "aceitação". Uma pergunta relacionada recente foi feita por Niel de Beaudrap.

Minha pergunta é a seguinte:

Sabemos se NL L? Ou essas duas classes são consideradas incomparáveis?

Dai Le
fonte

Respostas: