3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Max
    Sep 27 '11 at 21:22
  • $\begingroup$ @Max: Yes. The problem is the other inclusion (which is assumed not to hold, but we don’t know how to prove that). $\endgroup$ Sep 28 '11 at 10:03
  • $\begingroup$ Related: An oracle relative to which EXP(NP) = BPP -- cstheory.stackexchange.com $\endgroup$
    – nekketsuuu
    Dec 14 '17 at 0:33
7
$\begingroup$

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}$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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