ECCC-Report TR00-081https://eccc.weizmann.ac.il/report/2000/081Comments and Revisions published for TR00-081en-usFri, 22 Sep 2000 20:15:49 +0300
Paper TR00-081
| On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems |
Shin Aida,
Rainer Schuler,
Tatsuie Tsukiji,
Osamu Watanabe
https://eccc.weizmann.ac.il/report/2000/081In this paper we separate many-one reducibility from truth-table
reducibility for distributional problems in DistNP under the
hypothesis that P neq NP. As a first example we consider the
3-Satisfiability problem (3SAT) with two different distributions
on 3CNF formulas. We show that 3SAT using a version of the
standard distribution is truth-table reducible but not many-one
reducible to 3SAT using a less redundant distribution unless
P = NP.
We extend this separation result and define a distributional
complexity class C with the following properties:
(1) C is a subclass of DistNP, this relation is proper unless
P = NP.
(2) C contains DistP, but it is not contained in AveP unless
DistNP is contained in AveZPP.
(3) C has a polynomial-time many-one complete set.
(4) C has a polynomial-time truth-table complete set that is
not polynomial-time many-one complete unless P = NP.
This shows that under the assumption that P neq NP, the two
completeness notions differ on some non-trivial subclass of DistNP.
Fri, 22 Sep 2000 20:15:49 +0300https://eccc.weizmann.ac.il/report/2000/081