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.

Improve this question
$\endgroup$
2
  • 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
    Commented Dec 22, 2015 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 Steinke
    Commented Dec 22, 2015 at 7:40

1 Answer 1

Reset to default
7
$\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.".

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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