From a quick skim of the literature (and complexity zoo), there doesn't seem to be a non-deterministic version of PP. Is there a reason for this (e.g. PP=non-deterministic PP?)

Edit: Perhaps I phrased the question poorly: I was thinking more along the lines of BPP's relation to MA? Is there an equivalent version of an interactive proof system where Merlin needs only convince Arthur with probability >1/2?

  • 2
    How would such a complexity class be defined? – Sasho Nikolov Oct 15 at 1:46
  • Perhaps I phrased the question poorly: I was thinking more along the lines of BPP's relation to MA? Is there an equivalent version of an interactive proof system where Merlin needs only convince Arthur with probability >1/2? – user138901 Oct 15 at 11:11
up vote 8 down vote accepted

It does not really make sense to define an “X-version of class Y”, this is a misguided viewpoint. You define classes because they are useful or interesting in whatever context you are investigating, not to fill a slot in an imaginary table. So, what would count as a nondeterministic version of PP depends very much on what you intend to do with the class.

Having said that, in view of $\mathrm{P^{\|PP}=PP}$, one reasonable option is to define a nondeterministic version of PP as $\mathrm{NP^{\|PP}}$, which equals $\exists\mathrm{PP}$.

Concerning the edit: $\exists\mathrm{PP}$ indeed coincides with the variant of MA with acceptance probability $>1/2$.

  • Thanks for the answer, but what does ||PP mean in this case? I can't find any references to it (in the complexity zoo or otherwise). Thanks again! – user138901 Oct 15 at 18:33
  • 1
    $\mathrm P^{\|X}$ denotes polynomial time with parallel (= nonadaptive) access to oracle $X$. – Emil Jeřábek Oct 16 at 8:06

PP is defined as a probabilistic class and we don't normally think of nondeterministic versions of any of these classes (as far as I'm aware). In a sense probabilistic classes and nondeterministic ones are already on the same spectrum -- let me illustrate. We can define a language to be in PP if there's a randomized poly-time TM ("RPTM") that on a yes instance accepts with $> 0.5$ probability and on a no instance accepts with $\leq 0.5$ probability. Similarly we can define a language to be in NP if there's a RPTM accepting yes-instances w.prob $> 0$ and accepting no-instances w.prob $0$. (Convince yourself of this if you haven't before.) BPP corresponds to probability thresholds $\geq 2/3$ and $\leq 1/3$ while RP corresponds to $\geq 1/2$ and $0$.

So you see, PP can already be viewed as a "nondeterministic" version of P, but with different requirements as compared to NP.

  • Perhaps I phrased the question poorly: I was thinking more along the lines of BPP's relation to MA? Is there an equivalent version of an interactive proof system where Merlin needs only convince Arthur with probability >1/2? – user138901 Oct 15 at 11:11

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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