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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy