| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 426629 | Information and Computation | 2007 | 13 Pages |
Under the assumption that NP does not have p-measure 0, we investigate reductions to NP-complete sets and prove the following:(1)Adaptive reductions are more powerful than nonadaptive reductions: there is a problem that is Turing-complete for NP but not truth-table-complete.(2)Strong nondeterministic reductions are more powerful than deterministic reductions: there is a problem that is SNP-complete for NP but not Turing-complete.(3)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 many-one complete problem for NE is complete under one-to-one, length-increasing reductions that are computed by polynomial-size circuits.
