FOM: History of NP completeness

[Stephen Cook]

Lou van den Dries writes:	 
	 
	 If I am not mistaken, classical algorithms like Euclid's for gcd,
	 and the basic facts of decimal representation have attracted from
	 quite a while back some attention as to number of steps
	 required, etc. Anyway, number theory has always been full of
	 algorithms. It seems plausible to me that the experience gained in suc
	h
	 matters had a distinct influence in the rise of complexity theory, and
	 the
	 interest in problems like P=NP. But I'd be interested in hearing
	 what Steve Cook would have to say about this.

For me, the precursor of NP completeness was r.e. completeness.  My thesis
advisor, Hao Wang, had recently shown (with others) that the AEA case for
predicate calculus satisfiability is co- r.e. complete, essentially by showing that
such a formula could express the condition that a Turing machine does not
halt.  Hence it occured to me that the propositional satisfiability problem is
complete in a different sense, because a propositional formula can assert that
a nondeterministic Turing machine halts within a specified number of steps.

In my 1971 paper, the only problems I prove NP complete are SAT, 3SAT, and
the subgraph problem (essentially the clique problem).  But number theory
comes in a little:  I mention as an open problem (in modern terminology)
the question of whether the nonprimes are NP-complete. ( I also mention
the graph isomorphism problem as open.) 

My 1966 PhD thesis concerned integer algorithms; specifically the complexity
of integer multiplication.  But of course there was no question of infeasibility 
here.

Levin's original 1973 paper on NP completeness doesn't mention number
theory, except that the Diophantine equation problem is an example of an
unsolvable problem.  His six NP complete problems concern satisfiability
and combinatorics.	 

Other historical notes:  In the 1960's, Jack Edmonds coined the term
"good algorithm" for a polynomial time algorithm, in conjunction with
his graph matching algorithm.   In the late 1960's Michael Rabin was
trying to prove an exponential lower bound on all possible algorithms for
the Travelling Salesman Problem.

Of course there was early computer science interest in the possible infeasibiliy	 
of number theory algorithms.   Knuth's  major opus  "The Art of Computer 
Programming", Vol 2 (c 1969) has a section on integer factoring. This inspired
Pratt's proof that the set of primes is in NP.  Diffie and Hellman used the
discrete log problem as the basis for a possible public key cryptosystem in 1976.

Steve Cook