# Is there a non-deterministic version of the complexity class PP?

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?

• How would such a complexity class be defined? – Sasho Nikolov Oct 15 '18 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 '18 at 11:11

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 '18 at 18:33
• $\mathrm P^{\|X}$ denotes polynomial time with parallel (= nonadaptive) access to oracle $X$. – Emil Jeřábek Oct 16 '18 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 '18 at 11:11