How is the time complexity of a non-deterministic Turing machine defined?

Question

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.

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

Answer 1

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.