7
$\begingroup$

In Sipser's textbook "Introduction to the Theory of Computation, Second Edition," he defines nondeterministic time complexity as follows:

Let $N$ be a nondeterministic Turing machine that is a decider. The running time of $N$ is the function $f : \mathbb{N} \rightarrow \mathbb{N}$, where $f(n)$ is the maximum number of steps that $N$ uses on any branch of its computation on any input of length $n$ [...].

Part of this definition says that the running time of the machine $N$ is the maximum number of steps taken by that machine on any branch. Is there a reason that all branches are considered? It seems like the length of the shortest accepting computation would be a better measure (assuming, of course, that the machine halts), since you would never need to run the machine any longer than this before you could conclude whether the machine was going to accept or not.

Improve this question
$\endgroup$
3
  • $\begingroup$ This question needs to state the definition of "decider". $\endgroup$
    – Raphael ♦
    Oct 8, 2012 at 8:21
  • $\begingroup$ @Raphael- My apologies; I assumed this was standard terminology. Wikipedia uses the term "decider" to refer to a Turing machine that always halts. $\endgroup$
    – templatetypedef
    Oct 8, 2012 at 16:57
  • $\begingroup$ It certainly is standard, but technical details may differ. The discussions below indicate that the formal definition better be here, because the one you cite depends on it. $\endgroup$
    – Raphael ♦
    Oct 8, 2012 at 20:08

3 Answers 3

Reset to default
6
$\begingroup$

Because you don't know ahead of time whether or not any given input is a 'yes' instance — that is, whether there exists any accepting path — it makes sense for the sake of uniformity to bound the run-time independently of any particular feature of the computational paths. Thus, it makes sense to require the worst-case behaviour to be polynomial time, regardless of whether or not any accepting paths exist.

Improve this answer
$\endgroup$
6
  • $\begingroup$ But then again, you don't know ahead of time whether or not the a machine will halt on all inputs. I'm not sure I see why we can assume that the machine will always halt, but not be able to reason about the paths on which it accepts. $\endgroup$
    – templatetypedef
    Jul 24, 2012 at 0:49
  • 1
    $\begingroup$ You cannot tell for every machine whether it will halt on all inputs. But for some machines, you can. Every machine deciding a problem deterministically in polynomial time certainly halts, for example; as does the most straightforward construction for a nondeterministic machine solving instances of SAT. $\endgroup$
    – Niel de Beaudrap
    Jul 24, 2012 at 0:51
  • $\begingroup$ I understand that you can decide whether some machines halt, but you could also decide whether some machines have at least one accepting computation on all inputs. I guess I'm not seeing why we're assuming the first of these but not the second. $\endgroup$
    – templatetypedef
    Jul 24, 2012 at 3:05
  • 2
    $\begingroup$ The first is given to you by the machine being a decider. $\endgroup$
    – Luke Mathieson
    Jul 24, 2012 at 8:09
  • $\begingroup$ @LukeMathieson- But if we assume the machine is a decider, it's mathematically well-defined to say "the length of the longest accepting path for a string of length $n$, or the length of the longest overall computation if no accepting path exists." Perhaps I'm being very dense, but I don't see why this definition would be problematic. $\endgroup$
    – templatetypedef
    Jul 24, 2012 at 17:19
3
$\begingroup$

Ah, but you don't know that the machine will select the shortest accepting path. All nondeterminism gives you is that the machine will select some accepting path, if at least one exists. So in the worst case it selects the longest.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ That's a good point, but could I then refine my question to ask "why isn't the time complexity equal to the length of the longest accepting computation?" That still might be shorter than the longest possible computation. $\endgroup$
    – templatetypedef
    Jul 24, 2012 at 0:24
  • 2
    $\begingroup$ That would presume that the TM accepts. The complexity is for any input of length $n$, regardless of whether the input is in the language. $\endgroup$
    – Luke Mathieson
    Jul 24, 2012 at 8:07
2
$\begingroup$

The machine in this definition is a decider, that means it does halt on all inputs and accepts if and only if the input is in its language. That means that the maximum lengths of all computation makes sense, and should be the measure investigated.

You are probably thinking of acceptors. Those are Turing machines that halt and accept on inputs in the language, and do anything (but halt and accept) on inputs outside of the language. In particular, they can never terminate; some definitions even demand (equivalently) that acceptors loop when they don't accept. In this case, runtime does only make sense for positive inputs, but you still have to choose the longest one.

You could, of course, discuss to empower nondeterminism to not only choose a path towards acceptance, but also a shortest one. The standard notion does not include this, however, so the machine might take the longest path.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I am aware that the machine is a decider and thus always halts. The main reason I bring up this question is that if there is an accepting computation, I don't understand why the time complexity factors in computation paths other than accepting paths. Does that make any sense? Or is that line of reasoning inherently flawed? $\endgroup$
    – templatetypedef
    Jul 24, 2012 at 17:20
  • $\begingroup$ @templatetypedef: I think what you say makes sense. Maybe it's just convenience in order not to have different definitions for positive and negative inputs. Maybe the definition is not well though through. I wonder whether Sipser respects his own definition later; in particular, NP TMs which guess and verify a solution have no longer polynomial runtime -- they can guess arbitrarily large instances, therefore runtime goes through the roof. $\endgroup$
    – Raphael ♦
    Jul 24, 2012 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.