Theoretical Computer Science

# Is there a problem currently known to be outside class $\mathsf{NP}\cup\mathsf{coNP}$ but inside $\mathsf{BPP}$?

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.

## Solution

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

• +0 – Is $P\neq NP\neq \Sigma_2^P=NEXP$ possible? — Nov 26, 2017 at 15:00