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 notions under a
{\em 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~\cite{LutzMayordomo96}, Ambos-Spies
and Bentzien~\cite{AmbosSpiesBentzien00}, and Pavan and
Selman~\cite{PavanSelman02b}. The proof of this result is a
significant departure from previous work.