(*) 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?

  • 1
    $\begingroup$ Have you checked A. Turing? Paper from 1937y. He have invented and descibed it. It may be hard to recover what was on his mind at the time. The rest is abit philosophical. $\endgroup$
    – Evil
    May 1 '19 at 1:45
  • 2
    $\begingroup$ It is hard to answer this question as it is, since it relates NDTM (a technical mathematical construct) to scientific development, with no clear basis of comparison. Specifically, the terms "universe of solution", "a certain problem" and "theorem" are used here without definition. NDTM are not only a description of a certain, very constraint problems (containment of a word in a formal language over a finite alphabet) but also of a certain, very constraint algorithm. It is definitely not a metaphor for science as a whole, or a representation of problem solving by process of elimination. $\endgroup$
    – Ariel
    May 5 '19 at 17:36
  • 1
    $\begingroup$ "The NTDM is able to follow, in parallel, all paths of the tree of the universe of solution." -- nope. "The problem therefore affords a polynomial solution since at every branch, it tells us where to go." -- nope. "So the concept of NDTM accounts for all future scientific development." -- nope. "therefore has no chance of being polynomial, no matter how science might advance." -- nope. $\endgroup$
    – Raphael
    May 5 '19 at 20:31
  • 1
    $\begingroup$ Please excuse my brevity, but your text is of the "not even wrong" variety; you clearly have not absorbed the requisite (formal) definitions well. Please go back and reread them closely; our reference question can be a starting point. $\endgroup$
    – Raphael
    May 5 '19 at 20:32
  • $\begingroup$ "why was the NDTM invented?" -- That's a very different question. Is that's what you truly want to ask? In that case, please remove from your post all the unrelated material. $\endgroup$
    – Raphael
    May 5 '19 at 20:32

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.

  • $\begingroup$ The Church-Turing thesis states that the effectively calculable functions (those that we can actually calculate) are precisely the Turing-computable functions. It it not the statement that "all reasonable models of computation are equivalent", as you claim. Admittedly, this is a very common misconception. $\endgroup$ Jun 5 '19 at 20:17
  • $\begingroup$ You rephrased the term but kept the same meaning. "Effectively calculated functions" is not a formal definition but rather intuitive principles that all reasonable (read: mechanical) models of computation follow. Wikipedia writes - "... the ... thesis states that the above three formally-defined classes of computable functions coincide with the informal notion of an effectively calculable function. ... the concept of effective calculability does not have a formal definition". $\endgroup$
    – Ariel
    Jun 6 '19 at 21:25
  • $\begingroup$ You might be confusing "effective computation" with the two concrete computational models proved to be equivalent to TMs by Church and Turing, but as far as I know (checked wikipedia and it seems to affirm), the "thesis" isn't used to refer to that proof. $\endgroup$
    – Ariel
    Jun 6 '19 at 21:28

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.