FOM: Re: Cook vs Karp on NP completeness
sacook at cs.toronto.edu
Mon Feb 9 16:09:10 EST 1998
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
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
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!).
More information about the FOM