3
$\begingroup$

I read different things online about this:

In Sipser, p. 283. The time-complexity of a NTM is defined as the maximum number of steps it uses on any branch on any input of length n. So this is only defined for a decider.

In other sources (like the lecture notes I inherited from my predecessor at the university I work at, and a number of pages online like e.g. here: http://www.mi.fu-berlin.de/wiki/pub/ABI/ComputabilityComplexity/Complexity.pdf), it is defined as the maximum over the minimum number of steps in a path leading to acceptance for strings of length n in the language, and 0 (or sometimes 1) if the language does not contain any strings of length n.

So in the latter, the runtime is considered to be the length of the shortest accepting path, if it exists and 0 (or 1) if it doesn't. This last part is giving me a headache.

But there is something strange in Sipser's definition too. The runtime on a string that is accepted may be exponential if at least 1 path in the tree that does not accept the string is exponential, even if 1 (or all) paths that accept the string are polynomial.

Which of both is now correct? (Part of my confusion originates from whether or not a problem in NP requires a NTM that halts on any input.)

[EDIT] (added an example of the second definition) Based on the 2nd comment below, I found a similar comment on their equivalence in Hopcroft, Motwani and Ullman on page 432. equivalence

But using this equivalence, is it then not possible to construct a halting TM for any non-halting one?

$\endgroup$
10
  • $\begingroup$ Sipser's definition is the usual one. I have never seen the other one. $\endgroup$ Dec 2 '21 at 21:23
  • $\begingroup$ If all you care about is defining NP, then you could use either definition — they're equivalent (for this purpose) since a Turing machine can time itself and reject if it hasn't terminated by some given allotted running time. $\endgroup$ Dec 2 '21 at 21:24
  • $\begingroup$ I edited my question based on your comment. I can intuitively follow your statement of turning that TM into a halting one, but could you not do that for any non-halting TM then? $\endgroup$
    – TM___
    Dec 3 '21 at 7:02
  • $\begingroup$ You need to know a computable bound on the running time. $\endgroup$ Dec 3 '21 at 7:18
  • $\begingroup$ Ok, so that is generally not always the case I guess. But it has to be the case for all NP problems then (since they have to accept strings in polytime). I'm not very confident about these statements though. Is there a more sound reasoning about when such a bound is computable? $\endgroup$
    – TM___
    Dec 3 '21 at 7:39
0
$\begingroup$

It's always possible to limit running time of any TM or NTM to a bound by counting number of steps of execution and rejecting if too much time was used, if your time bound is large enough that such counting is available. Note though that this requires counting the size of input and computing the number of steps after which the bound is exceeded, and then counting the number of computation steps actually used and rejecting if bound is exceeded. This could be difficult if you don't know constant factor associated to the bound, or if the asymptotic bound itself is not known. The constant factor can usually be estimated, it's only important that it's sufficiently large for the used machine. Typically you would avoid the problem with constant factors by measuring time by (only) counting how many times loops or recursively invoked branches in the algorithms are executed.

There is a risk of changing the problem and producing wrong answers if you do not know that all accepting paths accept before the time bound, and if you limit the running time anyway. This of course must be avoided.

I used to speculate whether it would be possible to solve the P=NP problem by declaring that P != NP, because time is measured differently in P compared to in NP, since concurrent computation can explore many alternatives in one time step where sequential computation must check and search them sequentially. But of course the question is not quite that simple, as you would also need to prove that simulators can't compensate for the difference.

$\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.