Abstract:
The Turing and many-one completeness notions for NP have been previously separated under measure, genericity, and bi-immunity hypotheses on NP. The proofs of all these results rely on the existence of a language in NP with almost everywhere hardness.

In this paper we separate the same NP-completeness notions under a partial bi-immunity hypothesis that is weaker and only yields a language in NP that is hard to solve on most strings. This improves the results of Lutz and Mayordomo (1996), Ambos-Spies and Bentzien (2000), and Pavan and Selman (2004). The proof of this result is a significant departure from previous work. We also use this theorem to separate the NP-completeness notions under a scaled dimension hypothesis on NP.

Journal Version:

• Theory of Computing Systems, 42(2):131-142, 2008.
  [PostScript | PDF | DOI link]

• Proceedings of the 19th IEEE Conference on Computational Complexity (Amherst, Massachusetts, June 21-24, 2004), pages 198-203. IEEE Computer Society Press, 2004.
  [PostScript | PDF | DOI link]

• Technical Report TR04-025, Electronic Colloquium on Computational Complexity, 2004.