0
$\begingroup$

Assume that a given turing machine $M$ accepts words in the language in $n^k$ or less steps, but words that aren't in the language are rejected in unknown number of steps (the machine might even loop).

$k$ is unknown.

Is $L(M)\in P$?

Well, obviously $L(M)$ is recognized in polynomial time. The question is whether it's possible to decide $L(M)$ in polynomial time.

It seems to me that the answer is no, but I can't figure a way to prove it.

$\endgroup$
1
$\begingroup$

It is indeed possible. Simulate $M$ for $n^k$ steps. If it has accepted so far, accept. Otherwise, reject. You can simulate $M$ for $n^k$ steps in polynomial time (perhaps $O(n^{2k})$), hence this is a polynomial time algorithm.

$\endgroup$
  • $\begingroup$ k is unknown, we just know that such a k exists. But I can't figure how to find it. $\endgroup$ – iTayb Jul 2 '17 at 19:41
  • 1
    $\begingroup$ This is absolutely not a problem. You are not required to construct an algorithm that converts $M$ into a polynomial time decider, you only need to show that if a polynomial time recognizer exists, then a polynomial time decider exists. $\endgroup$ – Yuval Filmus Jul 2 '17 at 19:42

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.