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.

  • 1
    $\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

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.