1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Nathaniel
    Jan 12 at 0:05
  • $\begingroup$ 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$? $\endgroup$
    – Ordoshsen
    Jan 12 at 11:01
  • $\begingroup$ 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. $\endgroup$
    – Ordoshsen
    Jan 12 at 11:05

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.