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

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?

• Sipser's definition is the usual one. I have never seen the other one. Commented Dec 2, 2021 at 21:23
• 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. Commented Dec 2, 2021 at 21:24
• 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? Commented Dec 3, 2021 at 7:02
• You need to know a computable bound on the running time. Commented Dec 3, 2021 at 7:18
• 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? Commented Dec 3, 2021 at 7:39