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