The notion of NP-completeness can be defined in two distinct ways. A language can be complete for NP under polynomial-time Turing reducibility (Cook completeness) or under the stronger notion of polynomial-time many-one reducibility (Karp-Levin completeness). Although natural examples of NP-complete languages are complete under both definitions, it is widely believed that the two notions of completeness are, in general, distinct: that is, there exists a language that is Cook NP-complete, but not Karp-Levin NP-complete. The conjecture implies that P ≠ NP, so one expects that it would be very difficult to prove.

The goal of this paper is to show that the above conjecture follows from a reasonable complexity-theoretic hypothesis. The precise formulation of this hypothesis--that NP does not have p-measure 0--is too complicated to give in this brief review. Its intuitive meaning is that NP contains a fairly large portion of the languages decidable in exponential time.

In addition to showing that this hypothesis implies that the two notions of NP-completeness are distinct, the authors argue for the reasonableness and explanatory power of the hypothesis itself by establishing some of its other consequences. For example, they show that if NP does not have p-measure 0, then nondeterministic exponential time is different from deterministic exponential time, and similarly for doubly exponential time.