TR06-039 Authors: John Hitchcock, A. Pavan

Publication: 19th March 2006 20:08

Downloads: 2189

Keywords:

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 reductions: there is a problem that is SNP-complete

for NP but not Turing-complete.

- Every problem that is many-one complete for NP is complete

under length-increasing reductions that are computed by

polynomial-size circuits.

The first item solves one of Lutz and Mayordomo's ``Twelve Problems in

Resource-Bounded Measure'' (1999).

We also show that every problem that is complete for NE is complete under one-to-one,

length-increasing reductions that are computed by polynomial-size circuits.