Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Is the following problem computable in polynomial time?
Input: $<M_1>$, encoding of a determinstic TM that runs in polynomial time ($L(M_1)\in P$)
Output: $<M_2>$, encoding of a determinstic TM that runs in polynomial time ($L(M_2)\in P$), and satisfies:
[EDIT 2]
No, and in particular $M_2$ does not exist in general.
Consider only TM's (and languages) that do not distinguish between the letters $0$ and $1$. Let's call them monochrome. Thus, membership of a word $w$ in a monochrome language depends only on $|w|$. Now let $L$ be a non-regular monochrome language in P. For example, $L$ can be the set of all words whose length is a square number.
Next, we exploit the fact that we use Turing machines (and not RAMs or whatever) and that the time bound is exactly $n$ (and not $O(n)$). In that time bound, all the TM $M_2$ can do on the witness word $w$ (by which I mean the special input of a given length $n$ for which $M_2$ runs in time $n$) is to read the input once from left to right. If at any step it does not go right, it cannot discern the length of $w$. As $L$ is by nature neither finite nor co-finite, $M_2$ must measure the length exactly.
So, at least on the witness words, $M_2$ acts like a DFA. Then, construct an NFA $A_1$ which simulates $M_2$ as long as $M_2$ only goes right. The NFA $A_2$ is obtained from $A_1$ by replacing all edge labels by $\{0,1\}$. Then $A_2$ recognizes $L$: For any input, $A_2$ behaves just like $A_1$ does for the respective witness word, including acceptance or rejection.
Thus, $L$ is regular, contradicting the choice of $L$.
