2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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}$... $\endgroup$ – Joshua Grochow Dec 22 '15 at 5:38
  • 2
    $\begingroup$ 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})$. $\endgroup$ – Thomas Dec 22 '15 at 7:40
6
$\begingroup$

In your initial use of it, there was no need for "As far as we know" - We do know that

promiseBPP ⊆ promiseS2P ​ ⊆ ​ promise - (Σ2 ∩ Π2)

holds.


If ​ ZPP = NP ​ then

NP ∪ coNP ​ = ​ ZPP ∪ coZPP ​ = ​ ZPP ∪ ZPP ​ = ​ ZPP ​ ⊆ ​ BPP ​ ⊆ ​ S2P ​ ⊆ ​ Σ2 ∩ Π2

, so as far as we know

NP ∪ coNP ​ ⊆ ​ BPP ​ ⊆ ​ Σ2 ∩ Π2

could hold.


If ​ NP = coNP ​ then ​ ​ ​ BPP \ (NP ∪ coNP) ​ = ​ BPP \ S2P ​ ⊆ ​ BPP \ BPP ​ = ​ { } ​ ,
in which case there are no problems "outside class ​ NP ∪ coNP ​ but inside BPP".
In particular, no problems are "currently known to be outside class ​ NP ∪ coNP ​ but inside BPP".

I'm also not aware of any languages L known to be in BPP for which
it's also known that if L is in ​ NP ∪ coNP ​ then ​ ​ ​ BPP ​ ⊆ ​ NP ∪ coNP ​ .

"Is exactly 1 of these 2 polynomials identically zero?" ​ is "a problem currently known to be"
inside BPP but not known to be in ​ NP ∪ coNP . ​ ​ ​ More generally, non-monotone
combinations of [problems in RP that aren't known to be in coNP] yield such problems.


There is an oracle relative to which BPP is not a subset of PNP,
so presumably ​ BPP ⊆ PNP ​ is not known to hold.
If that containment is indeed not known to hold, then there pretty much can't be any known
result to the effect that "All problems in BPP are reducible to amalgamations of NP problems.".

$\endgroup$
  • 1
    $\begingroup$ so there are only amalgamated problems and no natural ones? $\endgroup$ – Turbo Dec 22 '15 at 12:16
  • 1
    $\begingroup$ I'm not aware of any natural such problems. ​ ​ $\endgroup$ – user6973 Dec 22 '15 at 13:08
  • $\begingroup$ Is $P\neq NP\neq \Sigma_2^P=NEXP$ possible? $\endgroup$ – Turbo Nov 26 '17 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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