Theoretical Computer Science
cc.complexity-theory complexity-classes big-picture randomness polynomial-hierarchy
Updated Fri, 17 Jun 2022 17:26:06 GMT

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

Comments (3)

  • +1 – so there are only amalgamated problems and no natural ones? — Dec 22, 2015 at 12:16  
  • +1 – I'm not aware of any natural such problems. — Dec 22, 2015 at 13:08  
  • +0 – Is $P\neq NP\neq \Sigma_2^P=NEXP$ possible? — Nov 26, 2017 at 15:00  

External Links

External links referenced by this document:

References