Lutz, Jack H. and Mayordomo, Elvira (1992) Cook versus Karp-Levin: Separating Completeness Notions If NP Is Not Small. Technical Report TR92-24, Department of Computer Science, Iowa State University.
Cook versus Karp-Levin: Separating
Completeness Notions If NP Is Not Small
Jack H. Lutz and Elvira Mayordomo
Under the hypothesis that NP does not have p-measure 0 (roughly, that
NP contains more than a negligible subset of exponential time), it is
show n that there is a language that is polynomial-time Turing
complete (``Cook complete''), but not polynomial-time many-one
complete (``Karp-Levin complete''), for NP. This conclusion, widely
believed to be true, is not known to follow from P<>NP or other
traditional complexity-theoretic hypotheses.
Evidence is presented that ``NP does not have p-measure 0'' is a reasonable
hypothesis with many credible consequences. Additional such
consequences proven here include the separation of many truth-table
reducibilities in NP (e.g., k queries versus k+1 queries), the
class separation E<>NE, and the existence of NP search problems
that are not reducible to the corresponding decision problems.
Contact site administrator at: firstname.lastname@example.org