<p>By Valiant-Vazirani, NP is contained in BP dot Parity-P (which obviously contains Parity-P).
Moreover, Toda showed that PH is in BP dot Parity-P which is in P^(#P) (which is in PSPACE).</p>

<p>For lower bounds, I think both classes contain a class known as FewP which contains UP and is like NP but you ask that strings in the language have at most polynomially many accepting paths.</p>

<p>[Update: corrected typo BPP instead of BP]</p>

CC BY-SA 2.5
2010-08-17T22:21:15.553Z
A corollary of the containment PH in BPP dot Parity-P, is that Parity-P is not contained in the Poly Hierarchy unless that Hierarchy collapses.
Andy Drucker
CC BY-SA 2.5
2010-08-17T22:27:51.833Z
This follows because, if Parity-P is in Sigma_k-P, then PH is in BPP dot Sigma_k-P, which is contained in Pi_(k+1)-P. (this last containment follows from a straightforward 'operator' generalization of the result that BPP is in Sigma_2 P intersect Pi_2 P.)
Andy Drucker
CC BY-SA 2.5
2010-08-17T22:39:28.313Z
I think it's considered plausible that BPP dot Parity-P is contained in P^(Parity-P).  If this is true, then PH is contained in P^(Parity), which is contained in (Parity-P)^(Parity-P), which actually equals Parity-P.

What I'm not sure of is whether any papers on hardness vs. randomness give a hypothesis which implies BPP dot Parity-P contained in P^(Parity-P).
Andy Drucker
CC BY-SA 2.5
2010-08-17T22:42:08.637Z
Finally, Parity-P is distinguished from NP and other PH classes in that it's known to have worst-case-to-average-case reductions.  That is, if Parity-P is not in P, then it contains distributional problems that are average-case hard.  See Feigenbaum-Fortnow, "Random-self-reducibility of complete sets".
Andy Drucker
CC BY-SA 2.5
2010-08-18T12:24:13.857Z
@Emanuele+Andy: Can one of you describe what the class BPP⋅Parity-P is? Is this just the bounded-error-probabilistic version of Parity-P?
Niel de Beaudrap
CC BY-SA 2.5
2010-08-18T17:04:45.817Z
Here's the general idea: let C be a complexity class.  A language L is in (BPP dot C) if there exists a language S in C, consisting of encoded pairs (x, r), such that:

-if x is in L, then for 2/3 of all r, the pair (x, r) is in S;

-if x is not in L, then for 2/3 of all r, the pair (x, r) is not in S.

(Technically, the length of r depends on x and is required to be at most some polynomial in |x|.)
Andy Drucker
CC BY-SA 2.5
2010-08-18T17:05:05.130Z
So the (BPP dot) is thought of as an 'operator' that acts on complexity classes to produce new ones.  Often the BPP operator is denoted BP instead.  Searching for 'complexity operator BP' will bring up some google hits; a more systematic reference is the book 'Structural Complexity I' by Balcazar et al.
Andy Drucker
CC BY-SA 2.5
2010-08-17T22:02:22.450Z
2010-08-18T19:17:56.733Z
2010-08-18T19:17:56.733Z
Manu
<p><a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aSymbols#parityp">Parity-P</a> 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). Thus Parity-P is basically <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aP#pp">PP</a>'s stunted younger sibling: while PP counts whether or not the number of accepting paths of an NP-machine is a majority or not (<em>i.e.</em> the most-significant bit of that quantity), Parity-P indicates the least-significant bit of the number of accepting paths.</p>

<p>Like NP, Parity-P contains <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aU#up">UP</a> (which contains P, "probably" strictly so); and like NP, Parity-P is contained in PSPACE.</p>

<p><strong>Question.</strong> What are the best known joint upper and lower bounds for NP and Parity-P?</p>

<cc.complexity-theory><complexity-classes><np>
Best known joint containments for/by NP and Parity-P?
Niel de Beaudrap
# Best known joint containments for/by NP and Parity-P?

(Asked by: username_0 on 2010-08-17)

[Parity-P](http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aSymbols#parityp) 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). Thus Parity-P is basically [PP](http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aP#pp)'s stunted younger sibling: while PP counts whether or not the number of accepting paths of an NP-machine is a majority or not (*i.e.* the most-significant bit of that quantity), Parity-P indicates the least-significant bit of the number of accepting paths.

Like NP, Parity-P contains [UP](http://qwiki.stanford.edu/wiki/Complexity_Zoo%3aU#up) (which contains P, "probably" strictly so); and like NP, Parity-P is contained in PSPACE.

**Question.** What are the best known joint upper and lower bounds for NP and Parity-P?

**Tags:** cc.complexity-theory, complexity-classes, np


---

## 1 answers

### Answer by username_1 on 2010-08-17. Score: 17 | Accepted answer

By Valiant-Vazirani, NP is contained in BP dot Parity-P (which obviously contains Parity-P).
Moreover, Toda showed that PH is in BP dot Parity-P which is in P^(#P) (which is in PSPACE).

For lower bounds, I think both classes contain a class known as FewP which contains UP and is like NP but you ask that strings in the language have at most polynomially many accepting paths.

[Update: corrected typo BPP instead of BP]

> **Comments:**
> **username_2**: A corollary of the containment PH in BPP dot Parity-P, is that Parity-P is not contained in the Poly Hierarchy unless that Hierarchy collapses.  
> **username_2**: This follows because, if Parity-P is in Sigma_k-P, then PH is in BPP dot Sigma_k-P, which is contained in Pi_(k+1)-P. (this last containment follows from a straightforward 'operator' generalization of the result that BPP is in Sigma_2 P intersect Pi_2 P.)  
> **username_2**: I think it's considered plausible that BPP dot Parity-P is contained in P^(Parity-P).  If this is true, then PH is contained in P^(Parity), which is contained in (Parity-P)^(Parity-P), which actually equals Parity-P.  What I'm not sure of is whether any papers on hardness vs. randomness give a hypothesis which implies BPP dot Parity-P contained in P^(Parity-P).  
> **username_2**: Finally, Parity-P is distinguished from NP and other PH classes in that it's known to have worst-case-to-average-case reductions.  That is, if Parity-P is not in P, then it contains distributional problems that are average-case hard.  See Feigenbaum-Fortnow, "Random-self-reducibility of complete sets".  
> **username_0**: @Emanuele+Andy: Can one of you describe what the class BPP⋅Parity-P is? Is this just the bounded-error-probabilistic version of Parity-P?  
> **username_2**: Here's the general idea: let C be a complexity class.  A language L is in (BPP dot C) if there exists a language S in C, consisting of encoded pairs (x, r), such that:  -if x is in L, then for 2/3 of all r, the pair (x, r) is in S;  -if x is not in L, then for 2/3 of all r, the pair (x, r) is not in S.  (Technically, the length of r depends on x and is required to be at most some polynomial in |x|.)  
> **username_2**: So the (BPP dot) is thought of as an 'operator' that acts on complexity classes to produce new ones.  Often the BPP operator is denoted BP instead.  Searching for 'complexity operator BP' will bring up some google hits; a more systematic reference is the book 'Structural Complexity I' by Balcazar et al.  

---

