18

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?

Niel de Beaudrap
  • 8,821
  • 31
  • 70

1 Answers1

17

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]

Manu
  • 7,659
  • 3
  • 37
  • 42
  • 5
    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 Aug 17 '10 at 22:21
  • 4
    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 Aug 17 '10 at 22:27
  • 4
    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 Aug 17 '10 at 22:39
  • 4
    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 Aug 17 '10 at 22:42
  • @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 Aug 18 '10 at 12:24
  • 3
    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 Aug 18 '10 at 17:04
  • 3
    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 Aug 18 '10 at 17:05