I'm reading Arora Barak and in that it is written that when $O \in \mathrm{P}$, then $\mathrm{P}^O = \mathrm{P}$. Can this be generalized? Intuitively, I think that $\mathrm{NP}^\mathrm{NP} \neq \mathrm{NP}$ but $\mathrm{EXP}^\mathrm{EXP} = \mathrm{EXP}$. Am I right? Any elaboration on the same would be appreciated.


1 Answer 1


No, $\mathsf{EXP^{EXP}=2EXP}$, a set of languages decidable in $O\left(2^{2^{\mathrm{poly}(n)}}\right)$ time.

This is just because you can give exponentially long input to an oracle which can solve it. So, the total power is $\exp(\exp(n))\ne \exp(n)$.

To see why $\mathsf P$ is self-low just take a machine that can run quadratic time and give to it the same oracle. While the resulting machine will be able to solve all languages in $\mathsf{DTIME}(n^4)$ it is still polynomial. Generalizing, $\mathrm{poly}(\mathrm{poly}(n))=\mathrm{poly}(n)$.

Was wrong, now understood that this is the only way to make machine that faster. Thanks to Ariel.

P.S. There is a parsimonious exp-time reduction from $\mathsf{2EXP}$-complete problem to an exponentially longer $\mathsf{EXP}$-complete problem.

  • 2
    $\begingroup$ Asking exponentially many queries does not necessarily require double exponential power, the problem is that the queries can be exponentially long. $\endgroup$
    – Ariel
    Sep 14, 2017 at 13:33
  • 1
    $\begingroup$ My logic was an $EXP$ machine can ask $2^{O(n)}$ queries to the oracle, and each oracle would itself solve an exponential time problem in a single step. So the total power would be $2^{O(n)} \times 2^{O(n)}$ which would still be in $EXP$ $\endgroup$
    – GARY
    Sep 15, 2017 at 7:58
  • $\begingroup$ So, $EXP^{EXP} = EXP$ is true? I'm sorry I don't get the exponentially long queries part. $\endgroup$
    – GARY
    Sep 16, 2017 at 3:57
  • 1
    $\begingroup$ @Gary, you can solve EXP-complete problem of length $2^n$ using the oracle. You can reduce 2EXP-complete problem of length $n$ to an EXP-complete problem of length $2^n$. $\endgroup$
    – rus9384
    Sep 16, 2017 at 4:00
  • $\begingroup$ I just got it! Thanks a ton for clearing it out $\endgroup$
    – GARY
    Sep 16, 2017 at 4:03

Your Answer

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

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