patternMinor
$\mathsf{2EXP} = \mathsf{EXP}^{\mathsf{EXP}}$?
Viewed 0 times
mathsfexp2exp
Problem
It is clear that any language in $\mathsf{EXP}^{\mathsf{EXP}}$ can be computed in $\mathsf{2EXP} = \mathsf{DTime}(2^{2^{\mathsf{poly}(n)}})$.
My question is whether the converse is true: is $\mathsf{2EXP} \subseteq \mathsf{EXP}^{\mathsf{EXP}}$?
My question is whether the converse is true: is $\mathsf{2EXP} \subseteq \mathsf{EXP}^{\mathsf{EXP}}$?
Solution
Consider the problem
$$A^f =
A_{TM}^f =
\{\langle M,x,t \rangle \mid
M\in DTM \text{ and }
M(x) \text{ halts and accepts in } f(|t|) \text{ steps}\}.$$
Now
$L^{\exp}$ is complete for $\mathsf{EXP} = \mathsf{DTime}(\exp (n^{O(1)}))$ and
$L^{\exp\exp}$ is complete for $\mathsf{2EXP} =\mathsf{DTime}(\exp\exp(n^{O(1)}))$.
We show that $L^{\exp \exp}$ is in $\mathsf{EXP}^\mathsf{EXP}$.
Given $\langle M,x,t \rangle$,
we simply write $\langle M,x,1^{\exp(|t|)} \rangle$ on the query tape and
ask it from $L^{\exp}$ and return its answer as output.
This algorithm is in $\mathsf{EXP}^\mathsf{EXP}$, therefore $\mathsf{2EXP} \subseteq \mathsf{EXP}^\mathsf{EXP}$.
$$A^f =
A_{TM}^f =
\{\langle M,x,t \rangle \mid
M\in DTM \text{ and }
M(x) \text{ halts and accepts in } f(|t|) \text{ steps}\}.$$
Now
$L^{\exp}$ is complete for $\mathsf{EXP} = \mathsf{DTime}(\exp (n^{O(1)}))$ and
$L^{\exp\exp}$ is complete for $\mathsf{2EXP} =\mathsf{DTime}(\exp\exp(n^{O(1)}))$.
We show that $L^{\exp \exp}$ is in $\mathsf{EXP}^\mathsf{EXP}$.
Given $\langle M,x,t \rangle$,
we simply write $\langle M,x,1^{\exp(|t|)} \rangle$ on the query tape and
ask it from $L^{\exp}$ and return its answer as output.
This algorithm is in $\mathsf{EXP}^\mathsf{EXP}$, therefore $\mathsf{2EXP} \subseteq \mathsf{EXP}^\mathsf{EXP}$.
Context
StackExchange Computer Science Q#12248, answer score: 8
Revisions (0)
No revisions yet.