Under the assumption that NP does not have p-measure 0, we investigate reductions to NP-complete sets and prove the following: - Adaptive reductions are more powerful than nonadaptive reductions: there is a problem that is Turing-complete for NP but not truth-table-complete. - Strong nondeterministic reductions are more powerful than deterministic ... more >>>