HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaMinor

Why does NTIME consider the length of the longest computation?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whythentimecomputationlengthconsiderdoeslongest

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#2887, answer score: 6

Revisions (0)

No revisions yet.