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:

  • $L(M_1)=L(M_2)$ (they decide the same language)
  • $\forall n\exists w\in\{0,1\}^n : \text {Time} (M_2,w)=n$ (there exists an input of any length on which the TM runs in linear time)
  • $\begingroup$ To be honest, at the moment I can't even see if such a $M_2$ always exists, let alone if it can be computed (and in PTIME). $\endgroup$ – chi Mar 20 '18 at 14:25

[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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.