We use hypotheses of structural complexity theory to separate various NP-completeness notions. In particular, we introduce an hypothesis from which we describe a set in NP that is Turing complete but not truth-table complete. We provide fairly thorough analyses of the hypotheses that we introduce. Unlike previous approaches, we make ... more >>>

We prove that if for some epsilon > 0 NP contains a set that is DTIME(2^{n^{epsilon}})-bi-immune, then NP contains a set that 2-Turing complete for NP but not 1-truth-table complete for NP. Lutz and Mayordomo (LM96) and Ambos-Spies and Bentzien (AB00) previously obtained the same consequence using strong hypotheses involving ... more >>>

The Turing and many-one completeness notions for $\NP$ have been previously separated under {\em measure}, {\em genericity}, and {\em 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 ... more >>>