The following definition [Gur91a][BG93] [BG95] is an elaboration of a definition in [VL88].
A distributional decision problem 
is
solvable in randomized ap-time if
is decidable by a randomized algorithm
in time polynomial on 
-average with a certifiable,
nonrare good-input domain. Denote by RAP the class of
all such problems.
A distributional search problem 
is solvable in
randomized ap-time if
there is a randomized algorithm solving
in time polynomial on -average.
The randomized reductions defined in Definition
4.2
are closed for randomized ap-time and they are transitive.
To see this, we first note that the composition 
of randomized algorithms uses random sequence 
, where
is the random sequence used by 
on input 
and
is the random sequence used by 
on input 
.
We then note that certifiable good-input domains compose. Finally,
we note that
randomized algorithms are deterministic algorithms on good-input
domains.
So randomized reductions are deterministic reductions
on good-input domains and so, similarly to Lemma 3.6,
it is straightforward to show the following lemma for distributional
decision problems. The lemma is also true for search problems.
Using ap-time randomized reductions, it was shown by Venkatesan and Levin [VL88] that a certain graph edge coloring problem with a flat distribution is complete for distributional NP search problems, and Blass and Gurevich [BG95] showed that a certain matrix transformation problem with a flat distribution is complete for DistNP. Some additional distributional problems are shown to be average-case NP-complete under randomized reductions in [VR92] Due to space limitations, exposition of these results will be given in a separate paper [Wan97]. To demonstrate the idea of using randomized reductions, we show that a certain halting problem with a flat distribution is complete for DistNP under p-time randomized reductions. We then show, in the next section, that polynomial-time sampling does not generate harder instances than uniformly picking instances at random.
The DISTRIBUTIONAL HALTING PROBLEM (VERSION 2)
consists of binary strings 
as instances.
The question is to decide whether
accept within 
steps.
Let 
denote the set of positive instances.
The probability 
of instance (positive or negative) is proportional to
,
where 
, 
, and 
.
Clearly is NP-complete and
is flat.
Let DH2 = 
.
Proof.is reducible to DH2 by a p-time randomized reduction as follows.
On input 
the reduction flips a
coin 
times to produce a random string 
, and then outputs
. More precisely,
we define a good-input domain 
by
.
Clearly, the rarity function 
and
is p-time computable, and so is certifiable.
Let 
, for 
.
For all 
, let 
.
Then 
is one-one and p-time computable. Clearly,
for all : 
iff 
.
To check the domination property, we note that
.
Thus, is a p-time randomized reduction from DH1 to DH2.
The randomized reduction constructed above is one-one and length-preserving within a polynomial. This indicates that, by Theorem 4.2, p-time randomized reductions are strictly more powerful than ap-time deterministic reductions.
