Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
Non-uniformly, NL is contained in parity-L: see http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W94/proc.pdf
