# Oracle Turing Machine EXP^EXP

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.

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.

• Asking exponentially many queries does not necessarily require double exponential power, the problem is that the queries can be exponentially long. Sep 14 '17 at 13:33
• 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$
– GARY
Sep 15 '17 at 7:58
• So, $EXP^{EXP} = EXP$ is true? I'm sorry I don't get the exponentially long queries part.
– GARY
Sep 16 '17 at 3:57
• @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$. Sep 16 '17 at 4:00
• I just got it! Thanks a ton for clearing it out
– GARY
Sep 16 '17 at 4:03