Cook versus Karp-Levin : separating 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 =PT-complete ("Cook complete"), but not =Pm-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 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.Preprin