Connecting strings in a graph is a PSPACE problem

Question

We define the following problem as:

Let $M$ be a TM with alphabet $\Gamma$, with $\{a,b,$ #$\} \subset \Gamma$.

We define, for every natural number $n$ the graph $G_{M,n}$ by:

$V_{M,n} = \{a,b\}^n$, the vertices

$E_{M,n} = \{(x,y) : x,y \in V_{M,n} $ and $M$ accepts the string $x$#$y$ with a run that requires at most $n^{73}$space$\}$

Now define the following language $L$:

$L = \{(<M>, x, y) : x,y \in \{a,b\}^*, |x| = |y|$ and $x,y$ are connected by a path in the above graph$\}$

I want to show $L \in PSPACE$, without using Savitch's theorem.

My attempt:

Define the following algorithm $M_0$

On input $(<M>, x, y)$ with $M$ with the above requirements:

1. Check if $M$ accepts the string $x$#$y$ in space $|x|^{73}$ or less; if so accept, else go to step 2.
2. Keep track of the set $Strings = \{x,y\}$ as a second tape.
3. For every string $z \in \{a,b\}^{|x|} - Strings$, add $z$ so $Strings$ and run $M_0$ on

a. $(<M>, x, z)$

b. $(<M>, z, y)$

If both accept, accept. If all strings in $\{a,b\}^{|x|}$ have not yielded accept, reject.

Now I think it's rather obvious that $L(M_0) = L$ but I'm unsure it solves it in poly. space:

Step 1. requires computing $|x|^{73}$ in unary, which takes poly. space in $|x|$. From here it is known that testing whether a machine accepts a string in some specific space, given in unary, is possible in poly. space when that unary representation is given in the input, using a universal machine. So step 1. requires poly. space in $|x|$.

Each step of the recursion in 2. requires keeping track of the strings tried which is fine. But the depth of the recursion seems to be $2^{|x|}$ which is problematic.

Can you suggest if this solution may still work, or a hint for another?

Answer 1

You say that you need to solve this "without Savitch", but what you're doing is (almost) implementing Savitch's proof within your algorithm.

That's perfectly fine, of course, as long as you're aware of that.

As for the space analysis of your algorithm - indeed, you present an exponential-space algorithm, in particular because you keep track of an exponential number of strings.

Consider the following change: in your subroutines (in the recursion), instead of limiting the set of vertices you're allowed to visit, how about limiting the number of steps you're allowed to take?

That is, define the subroutine that takes $<M>,x,z,t$ and checks whether $z$ is reachable from $x$ within $t$ steps, with $t$ encoded in binary.

Then, in the recursion, you can divide $t$ by $2$ at each step, thus obtaining a polynomial recursion depth.

This is, in fact, exactly how we prove Savitch's theorem, so it's no surprise that it works...