1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do your "tape slots" include the oracle tape? ​ (If no, then "he is still writing" does not mean he won't accept using <n tape slots.) ​ ​ ​ ​ $\endgroup$ – user12859 Feb 25 '17 at 23:18
  • $\begingroup$ @RickyDemer Yes, the oracle tape slots used count. Interestingly, BGS do not mention this caveat. $\endgroup$ – Lieuwe Vinkhuijzen Feb 25 '17 at 23:26
  • 1
    $\begingroup$ How does "the space hierarchy theorem for $Logspace^A \subsetneq PSPACE^{A[poly]}$" go "through as usual"? ​ (For all constants c_0 and c_1, (DSPACE(n^(c_0)))^(A[n^(c_1)]) can only write length-(n^(c_1)) queries to the oracle but Logspace^A can write longer queries to the oracle.) ​ ​ ​ ​ $\endgroup$ – user12859 Feb 25 '17 at 23:34
  • $\begingroup$ @RickyDemer (1/2) That's actually a very good question, I hadn't thought of that. Your objection goes through if we define $PSPACE^{A[poly]}\equiv \bigcup_{c}PSPACE^{A[n^{c}]}$. Then it looks to me like $PSPACE^{A[poly]}\subsetneq Logspace^A$. Let's define $PSPACE^{A[poly]}$ as the class of languages decidable by a TM $T$ for which there is a polynomial $s(n)$ such that $T$ uses at most $s(n)$ space on any tape, irrespective of that tape's role. $\endgroup$ – Lieuwe Vinkhuijzen Feb 26 '17 at 0:10
  • $\begingroup$ @RickyDemer (2/2) The class $Logspace^A$ will have to be defined differently from $PSPACE^A$, because we will have to allow polynomially long queries on the oracle tape, but we only allow logarithmic use of the work tape(s). These definitions will produce the paradox I am looking for if we can get the space hierarchy theorem to work, but I can't seem to do that. I tried incorporating the oracle tape used in the diagonalizing language, but to no avail. Can you think of a way to fix the SHT, or of good definitions? $\endgroup$ – Lieuwe Vinkhuijzen Feb 26 '17 at 0:24

Your Answer

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

Browse other questions tagged or ask your own question.