FOM: Awarding theorem-credits

[Vaughan Pratt]

>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?)

I've been too tied up with LICS PC duties the last few days to respond
much to anything, but could not let this pass.

There is no question in my mind that Cook has priority over Karp.
Karp's contributions, which came after Cook's SIGACT paper, were (i)
to greatly increase the number of NP-complete problems (Cook stopped at
around three, quite enough to make the basic point), and (ii) to refine
Cook reducibility to Karp reducibility by analogy with the refinement of
Turing reducibility to many-one reducibility in the definitions of Turing
degree and the arithmetic hierarchy.  Steve may have other contributions
of Karp to add to this list.

I am less clear about such questions in the case of Levin, and would
appreciate being shown the relevant page of a publication that would
clear up that question in my mind.

Vaughan Pratt