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