Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Parity-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 (rather than a zero or non-zero number of acceptance paths), and which is further restricted to work in logarithmic space. Solving a linear system of equations over ℤ2 is a complete problem for Parity-L, and so Parity-L is contained in P.

What other complexity class relations would be known, if Parity-L and P were equal?

share|cite|improve this question
up vote 26 down vote accepted

parity-$L$ is in $NC^2$ and parity-$L=P$ would mean that $P$ can be simulated in parallel $\log^2$ time or in $\log^2$ space (since $NC^2$ is in $DSPACE(log^2 n)$)

share|cite|improve this answer
Corollary: if Parity-L=P, then P≠PSPACE. – Niel de Beaudrap Aug 18 '10 at 10:05
@Niel I love that corollary! :) – Tayfun Pay Feb 12 '13 at 22:26

Well, evaluating Clifford group quantum circuits is complete under log space reductions for parity-L (See Aaronson and Gottesman, Physical Review A 70:052328, 2004). Now, let's use some tricks from measurement based quantum computation:

Evaluating clifford group circuits is in QNC^1. This is simply because there is no partial time ordering on measurements, and correction operations are simply calculated by parity of some subset of measurement results.

This would seem to imply that L^{QNC^1} contains P.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.