patternMinor
Oracle Turing Machine EXP^EXP
Viewed 0 times
turingoracleexpmachine
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#81218, answer score: 8
Revisions (0)
No revisions yet.