0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ wouldn't $\mathsf NP^{EXP}=N(P^{EXP})=NEXP?$ $\endgroup$ – blademan9999 Jun 8 '20 at 2:44
  • $\begingroup$ 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}$. $\endgroup$ – Ariel Jun 8 '20 at 8:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.