I know if there is a decidable relation R(x,y) for x in A, then A is semi-decidable. But how can I prove the relation is polynomial time?
For R(x,y), x is where M is a TM, y is the accepting configuration of M. Is this a polynomial-time relation?
1 Answer
$\begingroup$
$\endgroup$
5
For $R(x,y)$, $x$ is where $M$ is a TM, $y$ is the accepting configuration of $M$. Is this a polynomial-time relation?
Yes that is the right idea. Except $y$ should be a sequence of configurations that starts in the initial configuration and ends in the accepting configuration.
To see why this works, we have to consider the running time of the TM that accepts $R(x, y)$. First the TM looks at the input $x$, and then it looks at the sequence of configurations $y$. The sequence of configurations looks something like a table:
Tape at time 0: x1 x2 x3 .... xn 0 0 0 0 0 .... 0
^HEAD, state q0
Tape at time 1: x1 x2 x3 .... xn 0 0 0 0 0 .... 0
^HEAD, state q1
Tape at time 2: x1 1 x3 .... xn 0 0 0 0 0 .... 0
^HEAD, state q2
...
and so on. So how does our TM check if this is in $R(x, y)$? We should check to make sure that the initial configuration has $x$ on the tape. How long will this take? And then we should check that $y$ is a valid sequence of configurations of according to the transition behavior of $M$. How long will that take? Finally, we need to check that the last configuration in $y$ is accepting. How long will that take?
answered Feb 27, 2020 at 19:22
-
$\begingroup$ So it takes O(|x|) to check x is on the tape. O(|y|) to check y is a valid transition sequence. O(|x|) to check the last configuration in y is accepting, right? $\endgroup$– JohnCommented Feb 27, 2020 at 19:42
-
$\begingroup$ @John Mostly right -- except for Turing machines checking two strings for equality is quadratic instead of linear, so $O(|x|)^2$ to check $x$ is on the tape. What matters is that this is polynomial in $|x|$. $\endgroup$ Commented Feb 27, 2020 at 22:03
-
$\begingroup$ Also checking the last config is accepting means you check that the head is in an accepting state; that should be at most $O(|y|)$ instead of $O(|x|)$. Probably much less than $|y|$ but $|y|$ is an upper bound. $\endgroup$ Commented Feb 27, 2020 at 22:05
-
$\begingroup$ Does this mean that all semi-decidable problems are in NP? i don't? get it or do we need some extra conditions such as y has to be polynomially long? thanks! $\endgroup$– DeeDeeCommented Jun 22, 2020 at 1:26
-
$\begingroup$ @DeeDee Sorry I don't have time to write a detailed answer right now :( Try asking a new question! $\endgroup$ Commented Jun 22, 2020 at 2:04