Given two distributional problems, we wish to know which one is
computationally more difficult. The standard technique for such
comparisons is to find a reduction
from one problem to another.
For simplicity, we will focus on distributional decision problems.
Such a problem is comprised of a set of instances which are either positive
or negative for the underlying decision problem, and a probability
distribution on these instances. It is customary to only
specify the set of positive instances, and we are only concerned
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 polynomial time on
-average.
The following definitions are due to Levin [Lev86] and their current forms are from [Gur91].
The following lemma is straightforward [Gur91].
In the sequel, we will often use ``p-time" to denote ``polynomial-time", and ``ap-time" to denote ``average polynomial-time."
The following lemma is straightforward (see, for example, [Gur91] [Wan96]).
As indicated in [Lev86] and discussed
in [Gur91], instead of requiring a
reduction 
be p-time computable, one only
needs to require that be computable in ap-time.
This weakens the original definition in two ways: the reduction
is weaker and the domination is weaker.
The distribution is weakly dominated by the distribution
if there is a function 
such that for all , 
,
where is polynomial on -average.
