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 ... 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 >>>

We show that there is a language that is Turing complete for NP but not many-one complete for NP, under a {\em worst-case} hardness hypothesis. Our hypothesis asserts the existence of a non-deterministic, double-exponential time machine that runs in time $O(2^{2^{n^c}})$ (for some $c > 1$) accepting $\Sigma^*$ whose accepting ... more >>>