# $\mathsf{2EXP} = \mathsf{EXP}^{\mathsf{EXP}}$?

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}}$?

## migrated from cstheory.stackexchange.comMay 24 '13 at 18:11

This question came from our site for theoretical computer scientists and researchers in related fields.

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}$.