Paridad-L vs.LN

13

Parity-L, también conocido como L, es el conjunto de lenguajes reconocidos por una máquina de Turing no determinista que solo puede distinguir entre un número par o un número impar de rutas de "aceptación". Niel de Beaudrap hizo una pregunta relacionada reciente .

Mi pregunta es la siguiente:

¿Sabemos si NL L? ¿O se cree que estas dos clases son incomparables?

Dai Le
fuente

Respuestas: