Let $M$ be a Turing machine with oracle to $B$ that can decide $B$ in polynomial time. In the general case it means nothing, since we can just pass the input as a query to the oracle of $B$ and accept/reject according to its answer.

Now, we add the next limitation: given an input of length $n$, the queries' length can be at most $n-1$. Now, how does the fact that this TM with oracle to $B$ can decide $B$ in polynomial time imply that $B$ is in PSPACE?


From the definition we can check whether $0$ and 1 (or the empty word if you want)are in $B$ without any oracle access. So we do so and now construct a new Turing machine to decide $B$. We simulate the special machine for $B$ on our input. When it makes an oracle access to $B$ we intercept it (it is of size smaller then our input’s size) and now run another copy of the special Turing machine on this oracle. Finally we work with at most $n$ queries at each time for each size from $n$ to $1$. It can be observed that when we get to a query of size $1$ we can answer immediately and return to the left of the tape. As we won’t work with two oracle queries of the same size simultaneously it is actually a $\mathbf{PSPACE}$ machine. Moreover, we do not save any oracle answer we compute it each time it is asked - on the fly.

  • $\begingroup$ What do you mean by "we work with at most $n$ queries for each size from $n$ to 1"? $\endgroup$
    – Ariel
    Dec 14 '17 at 15:58
  • $\begingroup$ @Ariel in the worst case we get n-1 consecutive queries until no more and we get to a place the special turing machine will answer or we get to 0 and 1 and we answer then we will go back left at the recursion and answer the previous queries and continue to get more queries but we won’t more than one query of each size simultaneously. $\endgroup$ Dec 14 '17 at 16:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.