2
$\begingroup$

Language $L$ is in $\mathrm{P}$ if and only if there exists some Turing Machine $M$ such that for every word in $L$, $M$ either accepts or rejects it in polynomial time. Right?

But what if all we know about our language is that there exists TM $M'$ such that for every word in $L$, $M$ accepts it in polynomial time, but for words not in $L$ it might not halt at all, for example? Is existence of $M'$ enough to say that $L$ is in $\mathrm{P}$, and why/why not?

$\endgroup$
7
$\begingroup$

Suppose you have a problem $A$, and a TM $M$ which accepts all the words $w \in A$ within a polynomial time bound $p(|w|)$, and diverge (or reject) otherwise.

Then, we can craft a new TM $N$, which on input $w$ performs the following:

  • simulate $M$ with input $w$ for $p(|w|)$ steps;
  • if $M$ accepts, we make $N$ accept as well
  • otherwise we make $N$ reject

It is immediate to see that $N$ runs in polynomial time: simulating a step of $M$ requires polynomial time on the $M$ configuration (whose size remains polynomial during the whole simulation), and we only need a polynomial number of steps.

Further, $N$ decides $A$ by construction.

TL;DR: if we know we can only accept a word within a time bound $t$, we can set an alarm on $t$. When the alarm rings, if we have not accepted before, we know it's a reject.

Conclusion: your alternative definition of $P$ is equivalent to the regular one. I would argue that it is harder to work with in proofs, though.

$\endgroup$

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.