# What are the $EXP^{NP}$, $EXP^{PSPACE}$, and $EXP^{EXP}$ equal to

What are the $$EXP^{NP}$$, $$EXP^{PSPACE}$$, and $$EXP^{EXP}$$ equal to?

I suspect that their, NEXP, ESPACE and 2EXPtime respecitvely. And what bout $$NP^{EXP}$$

$$\mathsf{NP^{EXP}=EXP\subseteq NEXP \subseteq EXP^{NP}\subseteq EXP^{PSPACE}\subseteq EXP^{EXP} = 2EXP}$$
I suggest that you try proving these relationships yourself. $$\mathsf{NEXP\subseteq EXP^{NP}}$$ requires a simple padding argument, and for $$\mathsf{2EXP\subseteq EXP^{EXP}}$$ observe that the language $$L=\{\left(M,x,t\right) | \text{M accepts x within t steps}\}$$ is EXP-complete (when $$t$$ is encoded in binary). Anything more than that is probably hard, e.g. $$\mathsf{NEXP\subsetneq EXP^{NP}}$$ implies $$\mathsf{NP\subsetneq P^{NP}}$$ via a padding argument.
• wouldn't $\mathsf NP^{EXP}=N(P^{EXP})=NEXP?$ Jun 8 '20 at 2:44
• How do you define $N\left(\mathsf{P^{EXP}}\right)$? If it is the non deterministic version of polynomial time oracle machines then it is just $\mathsf{NP^{EXP}}$ written strangely. Generally, if two classes of languages characterized by certain types of Turing machines are equal, this does not mean that the non-deterministic version of these classes are also equal, consider e.g. $\mathsf{P=L}$ does not immediately imply $\mathsf{NP=NL}$. Jun 8 '20 at 8:57