<p>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 <span class="math-container">$&gt; 0.5$</span> probability and on a no instance accepts with <span class="math-container">$\leq 0.5$</span> probability. Similarly we can define a language to be in NP if there's a RPTM accepting yes-instances w.prob <span class="math-container">$&gt; 0$</span> and accepting no-instances w.prob <span class="math-container">$0$</span>. (Convince yourself of this if you haven't before.) BPP corresponds to probability thresholds <span class="math-container">$\geq 2/3$</span> and <span class="math-container">$\leq 1/3$</span> while RP corresponds to <span class="math-container">$\geq 1/2$</span> and <span class="math-container">$0$</span>.</p>

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

CC BY-SA 4.0
2018-10-15T11:11:30.107Z
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?
Hans Schmuber
CC BY-SA 4.0
2018-10-15T05:17:34.450Z
2018-10-15T05:17:34.450Z
usul
<p>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 <em>useful</em> or <em>interesting</em> 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 <em>do</em> with the class.</p>

<p>Having said that, in view of <span class="math-container">$\mathrm{P^{\|PP}=PP}$</span>, one reasonable option is to define a nondeterministic version of PP as <span class="math-container">$\mathrm{NP^{\|PP}}$</span>, which equals <span class="math-container">$\exists\mathrm{PP}$</span>.</p>

<p>Concerning the edit: <span class="math-container">$\exists\mathrm{PP}$</span> indeed coincides with the variant of MA with acceptance probability <span class="math-container">$&gt;1/2$</span>.</p>

CC BY-SA 4.0
2018-10-15T18:33:48.527Z
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!
Hans Schmuber
CC BY-SA 4.0
2018-10-16T08:06:05.530Z
$\mathrm P^{\|X}$ denotes polynomial time with parallel (= nonadaptive) access to oracle $X$.
Emil Jeřábek
CC BY-SA 4.0
2018-10-15T07:13:45.173Z
2018-10-15T12:43:50.400Z
2018-10-15T12:43:50.400Z
Emil Jeřábek
<p>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?)</p>

<p>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?</p>

CC BY-SA 4.0
2018-10-15T01:46:54.963Z
How would such a complexity class be defined?
Sasho Nikolov
CC BY-SA 4.0
2018-10-15T11:11:40.613Z
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?
Hans Schmuber
<cc.complexity-theory><complexity-classes><time-complexity>
Is there a non-deterministic version of the complexity class PP?
Hans Schmuber
# Is there a non-deterministic version of the complexity class PP?

(Asked by: username_0 on 2018-10-14)

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?

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

> **Comments:**
> **username_1**: How would such a complexity class be defined?  
> **username_0**: 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 answers

### Answer by username_3 on 2018-10-15. Score: 9 | Accepted answer

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$.

> **Comments:**
> **username_0**: 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!  
> **username_3**: $\mathrm P^{\|X}$ denotes polynomial time with parallel (= nonadaptive) access to oracle $X$.  

---

### Answer by username_2 on 2018-10-15. Score: 10

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.

> **Comments:**
> **username_0**: 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?  

---

