In this paper we separate many-one reducibility
from truth-table reducibility for distributional problems in DistNP
under the hypothesis that P not= 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.
<P>
We extend this separation result
and define a distributional complexity class C
with the following properties:

<OL>
<LI>
C is a subclass of DistNP,
this relation is proper unless P = NP.
<LI>
C contains DistP,
but it is not contained in AveP
unless DistNP is contained in AveZPP.
<LI>
C has a many-one complete set.
<LI>
C has a truth-table complete set
that is not many-one complete unless P = NP.
</OL>

This shows that
under the assumption that P not= NP,
the two completeness notions differ
on some non-trivial subclass of DistNP