<p>In <a href="https://en.wikipedia.org/wiki/Parity_P" rel="nofollow">Wikipedia</a> it is stated that it is not known if $\mathsf{P^{\oplus P} \mathrel{(=} \oplus P)}$ contains $\mathsf{NP}$, although it is known that $\mathsf{BPP^{\oplus P}}$ contains $\mathsf{PH}$.</p>

<p><strong>Questions</strong></p>

<ol>
<li>Is $\mathsf{\oplus P}$ expected to be contained in $\mathsf{PH}$? If so, at what level might it plausibly be?</li>
<li>Is there an analog of $\mathsf{\oplus P}$ in the diophantine hierarchy?</li>
</ol>

CC BY-SA 3.0
2016-02-22T08:19:10.253Z
1. Nowhere, of course. $\oplus P$ is not in PH at all unless PH collapses, by the $PH\subseteq BPP^{\oplus P}$ result you quote. Your claim that $PH\subseteq BPP^{NP}$ is nonsense. As for 2, it's totally unclear what kind of analogue you mean.
Emil Jeřábek
CC BY-SA 3.0
2016-02-22T08:27:24.953Z
What kind of diophantine hierarchy do you mean? This one? http://link.springer.com/article/10.1007%2Fs10958-012-1106-7
hirsch
CC BY-SA 3.0
2016-02-22T21:11:05.350Z
The only thing that comes to my mind about ${\bf BBP} ^{\bf NP}$ is that ${\bf NP}^{\bf BPP} \subseteq {\bf BPP}^{\bf NP}$. [Zachos and Furer, Probabilistic Quantifier vs distrustful adversaries. 1987]
Tayfun Pay
<cc.complexity-theory><complexity-classes><big-picture><np><polynomial-hierarchy>
$\oplus P$ status in polynomial hierarchy
Turbo
# $\oplus P$ status in polynomial hierarchy

(Asked by: username_0 on 2016-02-21)

In [Wikipedia](https://en.wikipedia.org/wiki/Parity_P) it is stated that it is not known if $\mathsf{P^{\oplus P} \mathrel{(=} \oplus P)}$ contains $\mathsf{NP}$, although it is known that $\mathsf{BPP^{\oplus P}}$ contains $\mathsf{PH}$.

**Questions**

1. Is $\mathsf{\oplus P}$ expected to be contained in $\mathsf{PH}$? If so, at what level might it plausibly be?
2. Is there an analog of $\mathsf{\oplus P}$ in the diophantine hierarchy?

**Tags:** cc.complexity-theory, complexity-classes, big-picture, np, polynomial-hierarchy

> **Comments:**
> **username_1**: 1. Nowhere, of course. $\oplus P$ is not in PH at all unless PH collapses, by the $PH\subseteq BPP^{\oplus P}$ result you quote. Your claim that $PH\subseteq BPP^{NP}$ is nonsense. As for 2, it's totally unclear what kind of analogue you mean.  
> **username_2**: What kind of diophantine hierarchy do you mean? This one? http://link.springer.com/article/10.1007%2Fs10958-012-1106-7  
> **username_3**: The only thing that comes to my mind about ${\bf BBP} ^{\bf NP}$ is that ${\bf NP}^{\bf BPP} \subseteq {\bf BPP}^{\bf NP}$. [Zachos and Furer, Probabilistic Quantifier vs distrustful adversaries. 1987]  

---

## 0 answers

