What's the purpose of the non-deterministic Turing machine?

Question

(*) Acronyms

NTDM := non-deterministic Turing machine. TM := deterministic Turing machine.

(*) Consider the following idea

The NTDM is able to follow, in parallel, all paths of the tree of the universe of solution. Suppose that in some point in time, for a certain problem, a new theorem is discovered that tells us that we need not worry about certain branches of the universe of solution because those branches yield no solution. Then in some future point in time, a new theorem appears telling us we need not worry about some other branches of the tree and so on. New theorems keep on being proved such that eventually there's only a single path to be followed in the tree of the universe of solution. The problem therefore affords a polynomial solution since at every branch, it tells us where to go.

So the concept of NDTM accounts for all future scientific development. Therefore, if a problem cannot be solved in polynomial time in the NDTM, then it's not in NP and therefore has no chance of being polynomial, no matter how science might advance.

This seems to be a good reason for the concept. Is there any flaw in this argument? In parallel, I'm interested in the question: why was the NDTM invented?

Answer 1

I will try to address why the concepts of NDTM and NP are useful, and possibly what motivated their study.

NDTM is one of many variants of turing mahcine. For example, the classical (deterministic) Turing machine can be equipped with multiple heads and tapes, randomness or quantum states. It can also be constrained by a limited alphabet, limited tape or pre-determined head-movements (see here).

A TM is said to decide a language (a set of words using a pre-defined alphabet), if it can halt on any input written on the tape, and accept precisely inputs belonging to the language. A language is called decidable if any TM decides it. Similarly, a function $f$ on natural numbers is said to be computable if there exists a TM which, given an input $n$, halts with $f(n)$ written on the input tape.

It turns out that all of the mentioned variations of TMs (including NDTM) are equivalent in the set of functions they can compute (similarly, the languages they can decide). This holds for other, much more different models than TMs, and has led to the Church-Turing thesis, which informally hypothesizes that any "reasonable" model of computation is equivalent to the classical Turing machine. In this aspect, NDTMs are useful as an example of fantastical computational models that are nonetheless as strong as a classical TM, supporting the Church-Turing thesis.

As far as I understand (see here and here for history), Turing himself did not focus on complexity classes, and so the previous reason might have been his sole motivation. However, later on it was discovered that different TM variants are not equivalent in the set of problems (languages and functions) they can solve in a certain amount of computation steps (time), bound on working-tape size (memory) and success probability. With this finer resolution, it turns out that the different models are very different, resulting in a zoo of complexity classes for problems.

I hope this is helps show why NDTMs (and the NP complexity class) are not a definite model for the problems science could potentially solve efficiently, but just one of many variations of computational models (less realistic than random and quantum machines, for example). There are, however, some reasons for why the specific class of nondeterministic polynomial time ($NP$) is such a popular attraction of the zoo:

1. It is relatively easy to explain and reason about. While researchers are working on many other open problems in complexity theory, the question of whether $P\neq NP$ requires only basic knowledge in math to understand, and the concept seems so intuitive that it invites many solution attempts from amateur researchers.
2. Whether a problem is solvable in polynomial time in a computational model is seen as an approximate measure of practical tractability (this is Cobham's thesis).
3. Any complexity bound derived by NDTMs can be seen as a bound on verification time by classical TMs (see here for why). Since classical TMs are used as models of practical computation, this has practical implications.
4. Many real-world important problems just happen to be not just in $NP$, but $NP$-complete. This means that if $NP$ is indeed a different complexity class than $P$, all of these important problems are not solvable in polynomial time with classical TMs.

Note that the fourth reason is unrelated to how realistic NDTMs are as a computational models (compared to classical TMs or other variants), or to any initial motivation for the invention of the concept. NP-complete problems are just surprisingly common in real life, and the scientific interest in them mirrors that.