Show that there is an oracle $A$ and a language $L \in \mathbf{NP}^A$ such that $L$ is not polynomial-time reducible to SAT even when the machine computing the reduction is allowed to access to $A$.
Warmup: Consider the language $N_1$ of properly parenthesized expressions over the alphabet $\Sigma$ consisting of two characters ‘$)$’ and ‘$($’ is in $\mathbf{L}$, where $\mathbf{L} = \mathrm{SPACE}(\log n)$ is the class of languages decidable in logarithmic space.
For instance, $( () ( (()) () ) )$ is in $N_1$, but $( ) ) ($ is not.
Now for the real problem: Consider the four-symbol alphabet
$$ \Sigma = \left\{\vphantom{\int_a^b} (, ), \langle, \rangle \right\}. $$
Let $N_2$ be the language of properly nested expressions over $N_2$. For instance, $( \langle ) \rangle$ is improper, but $\langle ( ) \rangle ( ( ) \langle \rangle )$ is proper. Prove that $N_2$ is in $\mathbf{L}$.
Say that a single-tape Turing machine $M$ is a recycler if $M$ never overwrites any blank space on the tape (i.e., it can only write on the portion of the tape containing the input).
Define the language:
$$ A_{\mathrm{recycler}} = \left\{ \langle M,x \rangle : M \textrm{ is a recycler that accepts } x\right\}. $$
Show that $A_{\mathrm{recycler}}$ is PSPACE-complete.
Show that $\mathbf{SPACE}(n) \neq \mathbf{NP}$. [Hint: We don’t know if either class is contained in the other.]