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

$\endgroup$
  • $\begingroup$ This question needs to state the definition of "decider". $\endgroup$ – Raphael Oct 8 '12 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 '12 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 '12 at 20:08
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.

$\endgroup$
  • $\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 '12 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 '12 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 '12 at 3:05
  • 2
    $\begingroup$ The first is given to you by the machine being a decider. $\endgroup$ – Luke Mathieson Jul 24 '12 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 '12 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.

$\endgroup$
  • 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 '12 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 '12 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.

$\endgroup$
  • $\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 '12 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 '12 at 18:24

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.