If $PSPACE^{SAT}=PSPACE$ and $PSPACE \subseteq EXP$, then why does $EXP^{SAT}$ not necessarily equal to $EXP$?

Question

I read the following claim:

• $PSPACE^{SAT}=PSPACE$
• $EXP^{SAT}$ is not necessarily the same as $EXP$

The first claim makes sense; $PSPACE \subseteq PSPACE^{SAT}$ trivially, and for any language $B \in PSPACE^{SAT}$ decided by an oracle machine $M_B$, we can define a non-deterministic machine $M'_B$ that works like $M_B$, except instead of querying an oracle, $M'_B$ instead guesses a witness and calls $M_{SAT}$ (a machine deciding $SAT$). It can easily be shown that $M'_B$ decides $B$ in polynomial space, and so $B\in NSPACE$. But from Savitch's Thoerem, $NSPACE=PSPACE$, and so $B \in PSPACE$. Thus, $PSPACE^{SAT}=PSPACE$.

I assumed that since $PSPACE \subseteq EXP$, then it should follow that $EXP^{SAT}=EXP$ as well. After all, it only needs to be shown that $EXP^{SAT}\subseteq EXP$ to prove the claim, but I can't see where the problem lies.

For that matter, my assumption was that if $X$ was any complexity class such that $X\subseteq Y$, then $Y^X=Y$. After all, any X-oracle doesn't allow Y to decide any language it couldn't already decide. But if the two claims are true, then obviously my assumption is wrong.

Answer 1

The fact that the base class can simulate the oracle does not mean that the oracle does not give additional power. Consider the polynomial hierarchy, $\mathsf{NP,NP^{NP},NP^{NP^{NP}}},...$ at the $i$'th level you get an oracle for the $i-1$ level, so following your line of thought we should not gain additional power. However a naive simulation of the oracle does not suffice, since taking the wrong path may lead us to accept an input outside the language (we need to be sure of the oracle's answers).

A class which is famously not low on itself is $\mathsf{EXP}$, since $\mathsf{EXP^{EXP}=2EXP}$. A naive simulation in your case fails for similar reasons, as a machine in $\mathsf{EXP^{SAT}}$ can ask the about the satisfiability of exponentially long formulas.