Prove that: For each language L that is accepted by a DTM in polynomial time, there is also a DTM M′ that decides L in polynomial time.

Question

According to one of my professors, the statement "For each language L that is accepted by a DTM in polynomial time, there is also a DTM M′ that decides L in polynomial time." is true, but i do not understand why, as the statement "For each language L that is accepted by a DTM, there is also a DTM M′ that decides L." is obviously false (e.g. the halting problem).

My first intuition was, that you could measure the runtime of a DTM and see if it accepts an input in polynomial time and if it does not, reject the input. The issue is, that i dont know how i would decide if a DTM spend more than a "polynomial" amount of time on an input.

Answer 1

Your first intuition is basically correct; you just need one extra insight. If $\ L\ $ is accepted by a DTM, $\ T_L\ $, say, in polynomial time, then there exists a polynomial $\ p_L\ $, which can be assumed to have integer coefficients, such that any word of $\ L\ $ of length $\ \ell\ $ will be accepted by $\ T_L\ $ in $\ p_L(\ell)\ $ steps or fewer. Let $\ M'\ $ be a DTM which does the following:

• Determines the length, $\ \ell\ $, of its input;
• Calculates $\ p_L(\ell)\ $;
• Simulates the operation of $\ T_L\ $ on the input and keeps count of the number of steps it has taken;
• If the number of steps the simulated $\ T_L\ $ has taken without having accepted the input reaches $\ p(\ell)+1\ $ then $\ M'\ $ declares that its input does not belong to $\ L\ $;
• Otherwise, the simulated $\ T_L\ $ can only have been found to accept the input in $\ p(\ell)\ $ steps or fewer, and $\ M'\ $ then declares that its input belongs to $\ L\ $.

Such a machine will decide $\ L\ $ in polynomial time.

The thing here is that you don't need to know what $\ p_L\ $ is to establish the existence of $\ M'\ $. You only need to know that it exists, and it must exist if $\ L\ $ is accepted in polynomial time by $\ T_L\ $.