Publication Date


Technical Report Number



Theory of Computation, Mathematics of Computing


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.