FOM: Re: Cook vs Karp on NP completeness

[Stephen Cook]

Concerning Joe Shipman's query on the origin of NP-completeness,
I introduced the notion in my 1971 STOC paper, and showed that SAT,
3-SAT, and subgraph isomorphism are NP-complete.  Based on
my paper, Karp showed that 20 or so other problems are NP-complete.
Karp also introduced the notion of polytime many-one reducibility
(as opposed to my polytime Turing reducibility), as well as the now
standard notation:  P and NP.

Meanwhile Levin came up with similar ideas independently of both
of us.

Steve Cook
	 

	 
	 Another case is the discovery of NP-completeness, originally 
	 attributed to Cook and Karp but now revised to co-credit Leonid 
	 Levin.  (Can Steve Cook confirm that his discovery and Karp's were 
	 independent?)  It is to be hoped that mathematical communication with 
	 and within Russia is so much better now that we won't have such confus
	ion 
	 for future important theorems (the old Tomsk-to-Omsk-to-Minsk-to-Pinsk
	 route popularized by Tom Lehrer in his song "Lobachevsky" reflected 
	 an unfortunate reality in the 60's!).
	 
	 Joe Shipman