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

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.

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

promiseBPP promiseS_{2}P promise - (_{2} _{2})

holds.

If ZPP = NP then

NP coNP = ZPP coZPP = ZPP ZPP = ZPP BPP S_{2}P _{2} _{2}

, so as far as we know

NP coNP BPP _{2} _{2}

could hold.

If NP = coNP then BPP \ (NP coNP) = BPP \ S_{2}P 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 P^{NP},

so presumably BPP P^{NP} 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.".

External links referenced by this document: