TR00-081 Authors: Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe

Publication: 22nd September 2000 20:15

Downloads: 2695

Keywords:

In 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.