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