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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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$– ArielSep 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$– GARYSep 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$– GARYSep 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$– rus9384Sep 16, 2017 at 4:00
-
$\begingroup$ I just got it! Thanks a ton for clearing it out $\endgroup$– GARYSep 16, 2017 at 4:03