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?

Improve this question
$\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, 2017 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, 2017 at 13:06
  • $\begingroup$ Oh, thanks, for some reason I thought direct simulation does not suffice. $\endgroup$
    – Ariel
    Nov 10, 2017 at 13:46

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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