Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-039 | 28th February 2006 00:00

Comparing Reductions to NP-Complete Sets

RSS-Feed

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.



ISSN 1433-8092 | Imprint