MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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


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?


Context: Slaughtering open problems.

share|cite|improve this question
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}$).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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