Cook versus Karp-Levin: Separating Completeness Notions If NP Is Not Small

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.

Abstract

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.


Subjects:
All uncategorized technical reports


ID code:
00000027
Deposited by:
Staff Account on 13 August 1992





Contact site administrator at: ssg@cs.iastate.edu