Is rejecting in polynomial time required for language to be in P?

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?

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.

StackExchange Computer Science Q#75970, answer score: 8