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 1"> c 1 ) accepting whose accepting computations cannot be computed by bounded-error, probabilistic machines running in time O ( 2 2 2 n c ) (for some 0"> 0 ). This is the first result that separates completeness notions for NP under a worst-case hardness hypothesis.