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?