Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|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
add comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.