# Open?: Bpp VS EXP^NP

Known:

BPP vs NEXP is open. BPP is strict subset of EXP^EXP.

Question:

Is BPP vs EXP^NP open?

If so, is there any class between EXP^NP, EXP^EXP concerning which vs BPP it's still open?

Thanks!

Context: Slaughtering open problems.

-
I'm not an expert, and maybe I'm having a dumb moment, but isn't BPP easily shown to be in EXP by simulating all possible coin flips? –  Max Sep 27 '11 at 21:22
@Max: Yes. The problem is the other inclusion (which is assumed not to hold, but we don’t know how to prove that). –  Emil Jeřábek Sep 28 '11 at 10:03

As far as I can see, BPP is not known to be distinct from $\mathrm{EXP}^\mathrm{NP}$.
A standard argument shows that $\mathrm{BPP}\ne\mathrm{BPEXP}$. (If $\mathrm{BPP}=\mathrm{BPEXP}$, then in particular $\mathrm{BPP}=\mathrm{EXP}$, hence $\mathrm{BPEXP}=\mathrm{EEXP}$ by padding, hence $\mathrm{EXP}=\mathrm{EEXP}$, contradicting the deterministic time hierarchy theorem.)
We have (by padding, using the corresponding results from the polynomial hierarchy) $\mathrm{BPEXP}\subseteq\mathrm{MAEXP}\subseteq\mathrm S_2^\mathrm{EXP}\subseteq\mathrm{ZPEXP}^\mathrm{NP}\subseteq\mathrm{NEXP}^\mathrm{NP}\cap\mathrm{coNEXP}^\mathrm{NP}$, so $\mathrm{BPEXP}$ is very close to being contained in $\mathrm{EXP}^\mathrm{NP}$, but not quite so.
There is also the related result by Buhrman, Fortnow, and Thierauf that $\mathrm{MAEXP}\nsubseteq\mathrm P/\mathrm{poly}$ (note that $\mathrm{BPP}\subseteq\mathrm P/\mathrm{poly}$).