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.
Journal Version:
Information and Computation, 205(5):694-706, 2007.
[DOI | PostScript | PDF]
Preliminary Versions:
Proceedings of the 33rd International Colloquium on Automata,
Languages, and Programming (Venice, Italy, July 10-14, 2006),
Lecture Notes in Computer Science 4051, pages 465-476.
Springer-Verlag, 2006.
[DOI]
Technical Report TR06-039,
Electronic Colloquium on Computational Complexity, 2006.