<p>May be this is trivial but I do not know the answer.</p>

<p>As far as we know $$\mathsf{BPP}\subseteq\mathsf{\Sigma}_2\cap\mathsf{\Pi}_2$$ holds.</p>

<p>As far as we know $$\mathsf{NP}\cup\mathsf{coNP}\subseteq\mathsf{BPP}\subseteq\mathsf{\Sigma}_2\cap\mathsf{\Pi}_2$$ could hold. Am I correct in this?</p>

<p>If so is there a problem that is currently known to be in $$\mathsf{BPP}\backslash\mathsf{NP}\cup\mathsf{coNP}=\mathsf{BPP}\cap\overline{\mathsf{NP}}\cap\overline{\mathsf{coNP}}$$ but conjectured to be in $\mathsf{P}$ just because of our belief $$\mathsf{P}=\mathsf{BPP}$$ should be true essential verdict?</p>

<p>That is is there a natural problem (not amalgamated ones) with a randomized poly algorithm nevertheless does not have a short <em>yes</em> or <em>no</em> certificate? A problem that comes close is <strong>PIT</strong> which is not known to be in $\mathsf{NP}$ but is in $\mathsf{coNP}$ which is the basis of the amalgamated problem (non-natural) below by Ricky Demer.</p>

CC BY-SA 3.0
2015-12-22T05:38:50.480Z
While it's true that it's possible that $\mathsf{NP} \cup \mathsf{coNP}$ could be contained in $\mathsf{BPP}$, if this is true then $\mathsf{NP}=\mathsf{RP}$ (exercise), and $\mathsf{PH}$ then collapses down to $\mathsf{BPP}$...
Joshua Grochow
CC BY-SA 3.0
2015-12-22T07:40:36.200Z
If $\mathsf{BPP} \setminus (\mathsf{NP} \cup \mathsf{coNP}) \ne \emptyset$, then $\mathsf{BPP} \ne \mathsf{P}$. So the belief that $\mathsf{BPP}=\mathsf{P}$ rules out the possibility of finding $L \in \mathsf{BPP} \setminus (\mathsf{NP} \cup \mathsf{coNP})$.
Thomas Steinke
<cc.complexity-theory><complexity-classes><big-picture><randomness><polynomial-hierarchy>
Is there a problem currently known to be outside class $\mathsf{NP}\cup\mathsf{coNP}$ but inside $\mathsf{BPP}$?
Turbo
# Is there a problem currently known to be outside class $\mathsf{NP}\cup\mathsf{coNP}$ but inside $\mathsf{BPP}$?

(Asked by: username_0 on 2015-12-22)

May be this is trivial but I do not know the answer.

As far as we know $$\mathsf{BPP}\subseteq\mathsf{\Sigma}\_2\cap\mathsf{\Pi}\_2$$ holds.

As far as we know $$\mathsf{NP}\cup\mathsf{coNP}\subseteq\mathsf{BPP}\subseteq\mathsf{\Sigma}\_2\cap\mathsf{\Pi}\_2$$ could hold. Am I correct in this?

If so is there a problem that is currently known to be in $$\mathsf{BPP}\backslash\mathsf{NP}\cup\mathsf{coNP}=\mathsf{BPP}\cap\overline{\mathsf{NP}}\cap\overline{\mathsf{coNP}}$$ but conjectured to be in $\mathsf{P}$ just because of our belief $$\mathsf{P}=\mathsf{BPP}$$ should be true essential verdict?

That is is there a natural problem (not amalgamated ones) with a randomized poly algorithm nevertheless does not have a short *yes* or *no* certificate? A problem that comes close is **PIT** which is not known to be in $\mathsf{NP}$ but is in $\mathsf{coNP}$ which is the basis of the amalgamated problem (non-natural) below by Ricky Demer.

**Tags:** cc.complexity-theory, complexity-classes, big-picture, randomness, polynomial-hierarchy
> **Comments:**
> **username_1**: While it's true that it's possible that $\mathsf{NP} \cup \mathsf{coNP}$ could be contained in $\mathsf{BPP}$, if this is true then $\mathsf{NP}=\mathsf{RP}$ (exercise), and $\mathsf{PH}$ then collapses down to $\mathsf{BPP}$...  
> **username_2**: If $\mathsf{BPP} \setminus (\mathsf{NP} \cup \mathsf{coNP}) \ne \emptyset$, then $\mathsf{BPP} \ne \mathsf{P}$. So the belief that $\mathsf{BPP}=\mathsf{P}$ rules out the possibility of finding $L \in \mathsf{BPP} \setminus (\mathsf{NP} \cup \mathsf{coNP})$.  

---

## 0 answers

