18
$\begingroup$

Parity-P 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'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 (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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
17
$\begingroup$

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]

Improve this answer
$\endgroup$
7
  • 5
    $\begingroup$ 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. $\endgroup$
    – Andy Drucker
    Aug 17, 2010 at 22:21
  • 4
    $\begingroup$ 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.) $\endgroup$
    – Andy Drucker
    Aug 17, 2010 at 22:27
  • 4
    $\begingroup$ 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). $\endgroup$
    – Andy Drucker
    Aug 17, 2010 at 22:39
  • 4
    $\begingroup$ 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". $\endgroup$
    – Andy Drucker
    Aug 17, 2010 at 22:42
  • 3
    $\begingroup$ 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|.) $\endgroup$
    – Andy Drucker
    Aug 18, 2010 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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