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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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, 2017 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, 2017 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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