

Lutz, Jack H. and Mayordomo, Elvira (1992) Cook versus KarpLevin: Separating Completeness Notions If NP Is Not Small. Technical Report TR9224, Department of Computer Science, Iowa State University.
Abstract
Cook versus KarpLevin: Separating
Completeness Notions If NP Is Not Small
Jack H. Lutz and Elvira Mayordomo
Under the hypothesis that NP does not have pmeasure 0 (roughly, that
NP contains more than a negligible subset of exponential time), it is
show n that there is a language that is polynomialtime Turing
complete (``Cook complete''), but not polynomialtime manyone
complete (``KarpLevin complete''), for NP. This conclusion, widely
believed to be true, is not known to follow from P<>NP or other
traditional complexitytheoretic hypotheses.
Evidence is presented that ``NP does not have pmeasure 0'' is a reasonable
hypothesis with many credible consequences. Additional such
consequences proven here include the separation of many truthtable
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: ssg@cs.iastate.edu
