<p>In his 1972 <a href="https://people.eecs.berkeley.edu/%7Eluca/cs172/karp.pdf" rel="nofollow noreferrer">paper</a>, Richard Karp provides a definition of NP (section 3, definition 4, p.91). It this the original definition of the class NP or is there a previous one?</p>
<p><strong>Edit</strong></p>
<p>Edmonds mentions the idea of backtracking in his 1965 <a href="https://math.nist.gov/%7EJBernal/p_t_f.pdf" rel="nofollow noreferrer">paper</a> and says it was already suggested by Berge in his 1957 <a href="https://www.pnas.org/content/pnas/43/9/842.full.pdf" rel="nofollow noreferrer">paper</a>. However, they do not formalize the notion of polynomial verifiers, although they explicitly use it.</p>

CC BY-SA 4.0
2020-08-04T08:48:42.600Z
Again not a direct definition of NP, but in [Mathematics and Computation](https://www.math.ias.edu/avi/book) Avi Wigderson suggests that Rabin and Scott's definition of nondeterministic automata in their [1959 paper](http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf) "inspired the later addition of nondeterminism to Turing machines, e.g., when extending P to NP".
Noam Zeilberger
CC BY-SA 4.0
2020-08-04T14:34:43.257Z
The name is Edmonds, not Edmond.
Emil Jeřábek
CC BY-SA 4.0
2020-08-13T01:59:36.860Z
Are Cook & Levin's original papers not what you're looking for? Cook's STOC '71 paper says "A set S accepted by some nondeterministic TM within poly time is P-reducible to DNF-Tautologies". Levin's '73 introduced "problem of sequential search type" as: "For a given x, find some y of length comparable w/ that of x s.t. A(x,y) holds", where A(x,y) is some property to be tested by an algorithm whose runtime is comparable with the length of x". Are you looking for when the definition of nondeterminism was first given? Or the class NP? Or the name NP? Something else?
Joshua Grochow
<np>
Who introduced the notion of Non-Deterministic Polynomial time?
Jérôme Verstrynge
# Who introduced the notion of Non-Deterministic Polynomial time?

(Asked by: username_0 on 2020-08-02)

In his 1972 [paper](https://people.eecs.berkeley.edu/%7Eluca/cs172/karp.pdf), Richard Karp provides a definition of NP (section 3, definition 4, p.91). It this the original definition of the class NP or is there a previous one?

**Edit**

Edmonds mentions the idea of backtracking in his 1965 [paper](https://math.nist.gov/%7EJBernal/p_t_f.pdf) and says it was already suggested by Berge in his 1957 [paper](https://www.pnas.org/content/pnas/43/9/842.full.pdf). However, they do not formalize the notion of polynomial verifiers, although they explicitly use it.

**Tags:** np
> **Comments:**
> **username_1**: Again not a direct definition of NP, but in [Mathematics and Computation](https://www.math.ias.edu/avi/book) Avi Wigderson suggests that Rabin and Scott's definition of nondeterministic automata in their [1959 paper](http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf) "inspired the later addition of nondeterminism to Turing machines, e.g., when extending P to NP".  
> **username_2**: The name is Edmonds, not Edmond.  
> **username_3**: Are Cook & Levin's original papers not what you're looking for? Cook's STOC '71 paper says "A set S accepted by some nondeterministic TM within poly time is P-reducible to DNF-Tautologies". Levin's '73 introduced "problem of sequential search type" as: "For a given x, find some y of length comparable w/ that of x s.t. A(x,y) holds", where A(x,y) is some property to be tested by an algorithm whose runtime is comparable with the length of x". Are you looking for when the definition of nondeterminism was first given? Or the class NP? Or the name NP? Something else?  

---

## 0 answers

