A distributional search problem is specified by 
,
where 
is a binary predicate and 
is a distribution.
Given an input 
, the search problem is to find 
(a witness)
such that 
is satisfied. is solvable in
average polynomial
time if there is a deterministic algorithm solving
the search problem
in polynomial time on -average.
Reductions on distributional search problems, which have
the desired properties, can be similarly
defined following the framework given
in [VL88].
The notion of ap-time reductions for search problems can
be similarly defined.
If is p-time computable and there is a polynomial 
such that 
,
then is called an NP predicate and
is called a distributional NP search problem.
A distributional NP problem , where is dominated
by a p-time computable
distribution, is said to be
complete if any other distributional NP search problem
with 
dominated by a p-time computable
distribution is
reducible to .
The search version of the distributional
halting problem is complete for distributional NP search
problems.
