Cook vs. Karp-Levin: Seperating Completeness Notions If NP Is Not Small

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 shown that there is a language that is P T-complete ("Cook complete "), but not P m-complete ("Karp-Levin complete"), for NP. This conclusion, widely believed to be true, is not known to follow from P 6 = 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 truthtable reducibilities in NP (e.g., k queries versus k+1 queries), the class separation E 6 = NE, and the existence of NP search problems that are not reducible to the corresponding decision problems