<p>Non-uniformly, NL is contained in parity-L: see <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W94/proc.pdf">http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W94/proc.pdf</a></p>

CC BY-SA 3.0
2011-09-24T06:29:11.800Z
The result has been extended by Reinhardt and Allender (see http://ftp.cs.rutgers.edu/pub/allender/nlul.pdf)
SamiD
CC BY-SA 3.0
2011-08-23T19:24:27.090Z
2011-08-23T19:24:27.090Z
Noam
<p>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 <a href="https://cstheory.stackexchange.com/questions/175/what-are-the-consequences-of-parity-l-p">related question</a> was asked by Niel de Beaudrap.</p>

<p>My question is the following:</p>

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

<cc.complexity-theory><counting-complexity>
Parity-L vs. NL
Dai Le
# Parity-L vs. NL

(Asked by: username_0 on 2011-08-23)

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](https://cstheory.stackexchange.com/questions/175/what-are-the-consequences-of-parity-l-p) 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?

**Tags:** cc.complexity-theory, counting-complexity

---

## 1 answers

### Answer by username_1 on 2011-08-23. Score: 19 | Accepted answer

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

> **Comments:**
> **username_2**: The result has been extended by Reinhardt and Allender (see http://ftp.cs.rutgers.edu/pub/allender/nlul.pdf)  

---

