21
$\begingroup$

I have two historical questions:

Who first described nondeterministic computation?

I know that Cook described NP-complete problems, and that Edmonds proposed that P algorithms are "efficient" or "good" algorithms.

I searched this Wikipedia article and skimmed "On the Computational Complexity of Algorithms," but couldn't find any reference to when nondeterministic computation was first discussed.

What was the first reference to the class NP? Was it Cook's 1971 paper?

Improve this question
$\endgroup$
5
  • 5
    $\begingroup$ NP was also invented more or less simultaneously by Levin on the other side of the iron curtain. In addition to Edmonds, Rabin and Cobham (each separately) also "introduced" P, though Edmonds was perhaps the most effective in justifying the viewpoint of P as "efficient". $\endgroup$
    – Joshua Grochow
    Commented Aug 29, 2015 at 1:40
  • $\begingroup$ Karps 1972 paper is considered a key counterpoint to Cooks paper showing that a bunch of problems are NP complete; in a sense Cook only showed that SAT was NP complete and it was not obvious after that paper how encompassing the concept might be. $\endgroup$
    – vzn
    Commented Aug 29, 2015 at 4:44
  • $\begingroup$ (further brief thought) so the two papers Cook/ Karp were like a "1-2 punch" on the TCS community/ collective understanding. also, on historical questions like this, sometimes concepts are "in the air" at the time & there is not a single unique/ definitive answer but a few nearly equally viable answers. another place to look is Turings 1936 paper on TMs, have never seen anyone analyze/ deconstruct conclusively rule out that nothing in the long paper comes close to nondeterminism. $\endgroup$
    – vzn
    Commented Aug 29, 2015 at 18:26
  • $\begingroup$ yet another angle (on this complex/ multidimensional topic): parallelism has many similarities to nondeterminism. $\endgroup$
    – vzn
    Commented Aug 30, 2015 at 1:41
  • $\begingroup$ It's also interesting to note that Godel recognized the importance of complexity and possibly foresaw P as the "efficient" algorithms. rjlipton.wordpress.com/the-gdel-letter $\endgroup$
    – evanb
    Commented Sep 16, 2015 at 7:16

3 Answers 3

Reset to default
31
$\begingroup$

I have always seen the notion of nondeterminism in computation attributed to Michael Rabin and Dana Scott. They defined nondeterministic finite automata in their famous paper Finite Automata and Their Decision Problems, 1959. Rabin's Turing Award citation also suggests that Rabin and Scott introduced nondeterministic machines.

Improve this answer
$\endgroup$
11
$\begingroup$

Here is what Odifreddi says on the issue:

"Our model of a Turing machine is deterministic, in the sense that the instructions are required to be consistent (at most one of them is applicable in any given situation). Randomizing elements in computing devices were introduced early on by Shannon [1948] and De Leeuw, Moore, Shannon and Shapiro [1956]. There are basically two models. Nondeterministic Turing machines behave, in an ambiguous situation where conflicting instructions might be applicable, by randomly choosing one of them: their computational power, at least for 0,1-valued functions (sets), does not exceed the power of deterministic ones. Probabilistic machines differ from nondeterministic ones in that the next state has a probability, and thus conflicting instructions do not have the same chance of being chosen by the machine."
[P. Odifreddi, Classical Recursion Theory, Vol. 1, page 50]

Note that the notion of nondeterminism in the sense of "there exists + verifier" existed in computability theory long before complexity theory, e.g. Kleene's normal form, arithmetical hierarchy. Other models of computation like Post canonical systems (known at least since 1943) and grammars are also nondeterministic. I think one can even push the notion to the time of Hilbert's epsilon calculus and choice operators.

About NP, I asked Steve Cook. The name NP for the class of nondeterministic polynomial-time computable problems was introduced by Richard Karp in his famous 1972 paper. Cook refers to the class of polynomial time nondeterministic Turing machine computable problems in his famous 1971 paper which defines polynomial time reductions and shows that there are complete problems, but without giving a name to the class.

Before his paper there was not much interest in problems computable in polynomial time by nondeterministic Turing machines, only after Karp's paper it became clear that so many natural problems are in NP. After Cook's paper some people got interested, particularly two who got interested early on (before Karp's paper came out) were Michael Rabin and Allan Borodin.

Karp's 1972 paper surprised people by showing how pervasive NP-completeness is among natural problems.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Using the term 'random' in this context is dangerous, it does not refer to randomness in the statistical sense, just the fact that a choice is left blank. $\endgroup$
    – reinierpost
    Commented Sep 1, 2015 at 8:53
  • $\begingroup$ @reinierpost, yest, it is confusing that he says nondeterministic machine selects the next state randomly (but in any case the nondeterministic machine is confusing by itself, that is why people typically prefer the verification definition of NP). $\endgroup$
    – Kaveh
    Commented Sep 1, 2015 at 18:53
  • $\begingroup$ I've never found it confusing. Maybe I'm so thoroughly confused I don't realize it. $\endgroup$
    – reinierpost
    Commented Sep 1, 2015 at 20:34
7
$\begingroup$

Rabin and Scott introduced the nondeterministic finite automata with their research paper published in IBM journal, April 1959. In the paper they mentioned:

we have adopted an even simpler form of the definition by doing away with a complicated output function and having our machines simply give “yes” or “no” answers. This was also used by Myhill, but our generalizations to the “nondeterministic,” “two-way,” and “many-tape” machines seem to be new.

Whole paper can be seen here: http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.