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:
- Check if $M$ accepts the string $x$#$y$ in space $|x|^{73}$ or less; if so accept, else go to step 2.
- Keep track of the set $Strings = \{x,y\}$ as a second tape.
- 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?