archives

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


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

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.

Full text available as:Postscript
Adobe PDF

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