3
$\begingroup$

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

$\endgroup$
7
$\begingroup$

No, $\mathsf{EXP^{EXP}=2EXP}$, a set of languages decidable in $O(2^{2^{poly(n)}})$ 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, $poly(poly(n))=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.

$\endgroup$
  • 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 '17 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 '17 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 '17 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 '17 at 4:00
  • $\begingroup$ I just got it! Thanks a ton for clearing it out $\endgroup$ – GARY Sep 16 '17 at 4:03

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.