For simplicity, we first consider distributional decision problems.
Such a problem is comprised of a set of instances that are either positive
or negative for the underlying decision problem, and a probability
distribution on these instances. It is customary to
specify only the set of positive instances, and we are concerned only
with instances with positive probability. Under such
a convention, we use 
to denote a distributional
decision problem, where 
is the set of all positive instances
with 
. The problem is to decide, for a given
instance with , whether 
. If
,
then is called a distributional NP decision problem.
Denote by AP the class of all distributional decision problems
such that is solvable in time polynomial on
-average.
Let 
be a function with input distribution .
It is reasonable to define the output distribution on 
,
denoted by 
, to carry all the weights
of those instances with 
. Namely,
for all 
, 
.
Denote by 
the distribution function of 
,
so 
.
Reductions from 
to 
should be
closed for AP, meaning that if
then so is .
One way to guarantee this is to require that efficiently
reduce 
to 
as in the
worst case, and that it should not reduce
``frequent" instances of to ``rare" instances of .
This means that the induced weight on the output 
should be bounded above (within a polynomial factor) by the
weight on according to the distribution of . Namely,
.
If 
, it follows that
there exists a distribution 
such that, for
all , it holds that
and 
,
which turns out to be sufficient for defining reductions.
Levin [Lev86] defined
reductions based on these ideas,
and their current forms, namely Definitions 3.2 and
3.3, were given by Gurevich in [Gur91a].
If a reduction is one-one, then it is straightforward to see that
iff 
.
This observation is useful in proving completeness results.
In the sequel, we will often use ``p-time" to
denote ``polynomial-time," and ``ap-time" to denote
``average polynomial-time."
Proof.(1) Let be a p-time reduction from to .
Then there are a distribution and a polynomial 
such that, for all , 
, and,
for all ,
.
Since , is
deterministically decidable in time 
where, for some
,
For any 
, 
. Since is p-time computable, there is a 
such
that 
for all but finitely many .
Let 
.
Then 
. It follows that
is polynomial on -average, and so
then also
is
Thus, deciding ``
?'' can be carried out in time 
plus
the time to compute 
, and so
. The proof of (2) is straightforward.
