Comparing reductions to NP-complete sets
[PostScript | PDF]
Abstract
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.
- Information and Computation, To appear.
- 33rd International Colloquium on Automata, Languages and Programming ,
LNCS 4051:465-476(2006).