# Graph based on strings of turing machine

For a $$\Sigma$$ with characters $$0,1,$$#$$,\sigma_1,...,\sigma_m$$. I have any $$M$$ that is a deterministic turing machine. Fix a $$n$$ (natural). i look at the following graph constructed from the turing machine $$M$$ (and the graph denoted by $$G(M)$$):

$$V$$ is all possible (binary) strings of length $$n$$ from characters $$0,1$$. So $$V$$ is $$2^n$$.

$$E$$ is $$(w_1,w_2)$$ for binary words $$w1,w2$$ that $$M$$ accepts as input the string $$w_1$$#$$w_2$$ and reaches accepting state and the calculation time is at most $$n^c$$ for some constant $$c$$ that will be detailed later.

Based on the definition of $$G(M)$$ for size $$n$$, i want to find for a given turing machine (deterministic) whether a specific pair of binary words $$w_1$$ and $$w_2$$ are of same length and are connected in the graph $$G(M)$$.

I need to do so using a limited memory given to me. We are given to solve this a turing machine which uses polynomial size memory.

How can this be verified in polynomial space?(not time, but if time, thats better).

I find this problem very intuitive to be solved using non deterministic turing machine. But i neede it done using deterministic one.

I am not sure how to begin and approach this?

• A few questions: is $n$ an input for your question? What is $c$ (your promised some missing details)? The complexity must be polynomial space in which variables? Jan 12 at 0:05
• first you denoted $n$ as the length of the input word, then as the size of the graph (which is a logarithm of the original $n$). So what is $n$? Jan 12 at 11:01
• I don't see how the graph comes into play at all. The question seems to be using PSPACE, verify that $w_1$ and $w_2$ are the same length and that $w_1\#w_2$ is accepted by a given Turing machine (in $n^c$ time). Both can be done in polynomial time of the size of the input strings. Jan 12 at 11:05