Baker, Gill and Solovay [1] gave an oracle $A$ relative to which $P^A=PSPACE^A$. The oracle is the very simple $PSPACE^A$-Complete language$$A = \{\langle M, x, 1^n \rangle | M^A \text{ accepts } x \text{ using }<n\text{ tape slots} \}.$$(This inductive definition of $A$ is sound because no machine can query beyond its means and ask $A$ whether he himself will accept his input string, because he would have to query $A$ and write $1^n$ on the oracle tape. If he is still writing, then clearly he has not accepted, and so $A$ says no.)The proof that $P^A=PSPACE^A$ is likewise simple: Suppose that $L\in PSPACE^A$. Then a $p(n)$-space machine $M$ accepts $L$. Given an input $x$, a $P^A$-machine $T$ for $L$ is: Write $\langle M, x, 1^{p(|x|)}\rangle$ on the oracle tape, query $A$, and accept iff $A$ says yes. So $PSPACE^A\subseteq P^A \quad\square$But in fact $T$ is not only a $P^A$-machine, $T$ is even a $LOGSPACE^A$-machine! Hence $PSPACE^A\subseteq LOGSPACE^A$. But the space hierarchy theorem says this cannot be the case. BGS even remark that the reduction $T$ performs can be performed in Logarithmic space, but they do not use that fact to come to my conclusion.Clearly I have made a mistake somewhere. Where?(One response might be that while a $PSPACE$ machine can use only polynomially much tape for its work, it can write exponentially long queries to the oracle. Denote by $PSPACE^{A[poly]}$ the class of languages solvable by a $PSPACE$-machine which makes only polynomially long queries to $A$. Then the space hierarchy theorem for $Logspace^A\subsetneq PSPACE^{A[poly]}$ goes through as usual)[1] Baker, Theodore, John Gill, and Robert Solovay. Relativizations of the P=?NP question. SIAM Journal on computing 4.4 (1975): 431-442.
Misunderstanding the Baker-Gill-Solovay oracle and obtaining $LOGSPACE^A=PSPACE^A$
complexity theory;complexity classes;space complexity;oracle machines;relativization