13

Parity-L, also known as $\oplus$L, is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths. A recent related question was asked by Niel de Beaudrap.

My question is the following:

Do we know if NL $\subseteq$ $\oplus$L? Or are these two classes believed to be incomparable?

Community
  • 1
Dai Le
  • 3,664
  • 1
  • 24
  • 37

1 Answers1

19

Non-uniformly, NL is contained in parity-L: see http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W94/proc.pdf

Noam
  • 9,369
  • 47
  • 58
  • 3
    The result has been extended by Reinhardt and Allender (see http://ftp.cs.rutgers.edu/pub/allender/nlul.pdf) – SamiD Sep 24 '11 at 06:29