John Hitchcock, A. Pavan

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