As indicated in [Lev86] and discussed
in [Gur91a], instead of requiring a
reduction 
be p-time computable, one
needs only 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, for all 
, 
,
for some function 
that is polynomial on -average.
The following definition was shown to be
the most general in the context of deterministic
many-one reductions [BG91] .
The proof of Lemma 3.6 is similar to that of Lemma 3.1, and can be found in [Gur91a] . It is not known whether ap-time reductions are more powerful than p-time reductions for DistNP problems, although one suspects that they are. One nice feature of ap-time reductions is that they can be used to establish completeness results for the class of distributional problems that are solvable by nondeterministic algorithms in average polynomial time. It is not known whether the same can be shown using p-time reductions. Studying such problems seems both logical and natural as noted in [Gur91a] [BCGL92] . The class of such problems, denoted by ANP, is a nondeterministic version of AP, which properly includes DistNP [WB93a] and is a logical average-case analog of NP. The proof of Theorem 3.4 can be easily modified to show the following result [WB93a] .
Thus, all average-case NP-complete problems are also ap-time complete for problems in ANP with p-time computable distributions. On the other hand, there are problems that are not in DistNP but are ap-time complete for problems in ANP with p-time computable distributions [WB93a] .
