Theory of computation often involves nondeterministic models of computation. Some examples include nondeterministic finite automata (NFAs), nondeterministic pushdown automata (PDAs), and nondeterministic Turing machines. Real computers, however, are deterministic (or at best, randomized).

What is the point of studying nondeterministic models of computation, given that they are unrealistic?

In particular, what is the point of the complexity class NP? Why should I care about nondeterministic machines running in polynomial time?


Excellent question! Nondeterminism first appears (so it seems) in a classical paper of Rabin and Scott, Finite automata and their decision problems, in which the authors first describe finite automata as a better abstract model for digital computers than Turing machines, and then define several extensions of the basic model, including nondeterministic finite automata. They seem to be completely unaware of what is bothering you. For them, nondeterminism is a way of reducing the number of states, and of simplifying the proofs of various closure properties.

Indeed, when simulating finite automata on an actual digital computer, NFAs can be simulated directly, by keeping track of the set of reachable states at any given point. This could be more efficient than converting the NFA to a DFA, especially if typically not many states are reachable.

Just as NFAs are equivalent to DFAs but are more state-efficient, so NTMs are equivalent to DTMs but are more time-efficient (here TM is short for Turing machine). However, in contrast to NFAs, there is no known way to efficiently simulate nondeterministic Turing machines on a digital computer (this is essentially the P vs NP question). Why then do we care about nondeterministic Turing machines?

There might be several reasons (for example, by analogy to complexity hierarchies in descriptive set theory and in recursion theory), but I think the most appealing one is the complexity class NP, whose natural definition is via nondeterministic Turing machines (there are other equivalent definitions using only deterministic Turing machines, which verify that an input belongs to the language using a polynomial length witness). It remains to convince you why NP is important.

Let's think of P as the set of (decision) problems which can be solved efficiently (there are various problems with this point of view, but let's ignore them). Some problems seem to be beyond P, for example SAT (here we encounter another problem which we ignore: SAT seems to be solvable efficiently on practical influences). How can we tell that SAT is not in P? The best answer we have found for this question is this:

SAT is in P if and only if Maximum Clique is in P if and only if Minimum Vertex Cover is in P if and only if ...

Individually, each of these problems seems hard, and this multitude makes the case more convincing for their inherent difficulty. It's enough to accept that one of SAT, Maximum Clique, Minimum Vertex Cover is difficult, and then it follows that all the rest are also difficult.

Where do the problems SAT, Maximum Clique, Minimum Vertex Cover come from? They are NP-complete problems, intuitively the "hardest" problems in NP (with respect to polynomial time reductions). So what the class NP allows us to do is to isolate a large class of problems which seem difficult.

Now some problems, like the halting problem, are provably difficult; in fact, uncomputable. But these problems are too difficult: the halting problem is much harder than SAT, so the fact that the halting problem is difficult has no bearing on SAT. Problems in NP are on the one hand not insanely difficult, and on the other hand some of them do seem too hard to solve efficiently.

Indeed, NP is only the first rung in a ladder of difficulty known as the polynomial hierarchy, which as mentioned before is inspired by other hierarchies such as the arithmetical hierarchy and the Borel hierarchy. In some sense, NP comes up naturally in this context, as the polynomially bounded version of the arithmetical hierarchy. (For another take, check out descriptive complexity theory.)

Finally, what about NPDAs? Why should we care about them? In a sense, we shouldn't, since in practice, most context-free languages we come in contact with (as grammars of programming languages) are deterministic context-free, and in fact belong to even more restricted subclasses. The importance of NPDAs lies in their equivalence with general context-free grammars: a language is context-free if and only if it is accepted by some NPDA. Since context-free grammars can be parsed efficiently, this also shows that NPDAs can be simulated efficiently by digital computers.

  • 3
    $\begingroup$ I feel it is worth mentioning that Dana Scott argues that nondeterminism wasn't such a good idea in a later paper. $\endgroup$
    – ttnick
    Nov 2 '18 at 14:47
  • 1
    $\begingroup$ Tbh I like the verifier/ deterministic prover way more since it easier to understand. And it makes the class NP interesting without having to care about actual problems in NP like SAT, Clique etc: If you understand P as the class of efficiently solvable problems, NP can be understood as the class of efficiently verifiable problems. This definition also generalizes better to the polynomial hierarchy IMO. $\endgroup$
    – Daniel
    Oct 27 '19 at 22:33

A complexity class is a set of problems (or languages) that can be solved on a given computational model with constraints on the use of resources (such as time and/or space for sequential computations). Therefore, it's pretty easy do define a complexity class. However, it's hard instead to define a meaningful complexity class, since the class

  • must capture a genuine computational phenomenon;
  • must contain natural and relevant problems;
  • should be ideally characterized by natural problems;
  • should be robust under variations in model of computation;
  • should be possibly closed under operations (such as complement etc).

Regarding nondeterminism and the class NP in particular, it captures an important computational feature of many problems: exhaustive search works. Note that this has nothing to do with efficiency in solving a problem: indeed, we will never solve a problem by using a brute force approach. The class also includes many natural, practical problems.

Besides the technical details (a non deterministic Turing Machine has a transition relation instead of a transition function, so that given the current configuration there can be several next configurations; moreover, for the nondeterministic Turing Machine there is an asymmetric accept/reject criterion), nondeterminism is usually explained, consistently with this perspective, in terms of an oracle that magically guesses a solution if one exists (it's like having a parallel computer spawning infinitely many processes, with each process in charge of verifying a possible solution).


Nondeterministic systems aren't unrealistic at all:

  1. Computer science should actually be called computing science: it deals with computation, not with computers. (To study computers, study electrical engineering.) Most computational systems we need to describe and analyze in computer science aren't computers. E.g. Facebook is not a computer, and it is highly nondeterministic. What is more, any interactive system is naturally described as a nondeterministic system: the system doesn't determine the outcome of choices left to the user, the user does, and the user isn't part of the system, so in a description of the system, such choices are nondeterministic.
  2. Modern computers aren't deterministic, either. They have many components (e.g. multiple CPUs) performing computational activities in parallel, and outcomes may be affected by timing and/or the occurrence of non-predetermined events.
  3. Even single CPU cores aren't deterministic these days; they pretend to be, but that pretense may fail.

Generally speaking, nondeterminism is the norm, not the exception, and it certainly isn't "unrealistic".

However, you're probably referring to a specific use of the term: nondeterministic automata as used in complexity theory.

When used in complexity theory, nondeterministic automata are used to describe search problems: they describe how to find a solution to the problem while omitting the exact method of scanning through the solution space to find one (which isn't part of the problem, but of the method chosen to solve it).

Once again, there is nothing "unrealistic" about systems that are subject to choices they don't control. Most systems are. It's the fiction of equating computing with strictly sequential machines that is unrealistic. It's a highly simplified, idealized notion of computing that practice doesn't always live up to.

  • $\begingroup$ There is a big difference in nondeterminism in complexity theory and in practical applications though and I would argue that they are two different concepts. In practical applications, nondeterminism describes that multiple outputs are possible for the same inputs, i.e. the output is a bit unpredictable. In complexity theory the output is actually predictable, since by definition we only take accepting runs (if they exist). $\endgroup$
    – Daniel
    Oct 27 '19 at 22:29
  • $\begingroup$ That depends on how it was taught to you. The way it was taught to me (and the only way that makes intuitive sense to me) is indeed that we only take accepting runs, not that the machine only makes accepting runs. E.g. a maze problem is the problem of finding some way out of the maze; a nondeterministic maze solver is a machine that can make any walk through a maze from the starting point, and the maze is solvable if at least one such walk gets us out of the maze. $\endgroup$ Oct 28 '19 at 8:41

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.