1
$\begingroup$

What are the largest classes which are low for EXP and NEXP?

For example: I am aware the class P, QP are low for EXP as well as NEXP. We also know that NP is not low for either of them.

Is class BPP low for EXP or NEXP? What is the largest oracle class we can provide to EXP (or NEXP) which doesn't increase its power?

$\endgroup$
3
  • $\begingroup$ can you provide a reference (or a short explanation if one exists) for "QP is low for EXP"? $\endgroup$ – Ariel Nov 10 '17 at 9:29
  • 1
    $\begingroup$ Class QP is closed under composition. For example: $QP^{QP} = QP$. You can try it out with $2^{\log ^{c} n}$ and $2^{\log ^{d} n}$ for constants $c$ and $d$. This gives a hint that QP is not very strong class. To your question, Every oracle call to class $QP$ can be simulated in time $2^{\log ^{c} n}$ for constant $c$. An EXP (or NEXP) machine can easily simulate all calls to QP oracle by staying within Exponential time. (only the constants will get bigger). $\endgroup$ – Pawan Kumar Nov 10 '17 at 13:06
  • $\begingroup$ Oh, thanks, for some reason I thought direct simulation does not suffice. $\endgroup$ – Ariel Nov 10 '17 at 13:46
2
$\begingroup$

$\mathsf{BPP=NEXP}$ is consistent with our current knowledge, thus, since $\mathsf{EXP, NEXP}$ are not low for themselves, it is not known whether $\mathsf{BPP}$ is low for them. A positive answer would imply $\mathsf{BPP\neq NEXP}$, and a negative answer would imply $\mathsf{P\neq BPP}$ (and in turn, that $\mathsf{P\neq NP}$), so currently, if you're looking for unconditional results, you will have no luck with $\mathsf{BPP}$.

Since even a (possibly weak) class as $\mathsf{BPP}$ is not known to be low for $\mathsf{EXP}$, you will need to look between $\mathsf{P}$ and $\mathsf{BPP}$ (which does not give you much wiggle room), or for classes who are currently incomparable with $\mathsf{BPP}$ (such as $\mathsf{QP}$ as you yourself noted, I doubt you can find a significantly stronger low class for EXP).

$\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.