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}$
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityWhat 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}$
The trivial implications are:
$\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.