Finding additional average-case NP-complete problems
has been a central research issue. The notions of p-time reducibility
and ap-time reducibility have played an important role in this study.
However, Gurevich [Gur87] observed
that NP-complete problems with ``flat'' distributions (see below for
a definition) cannot be complete for DistNP under p-time or
ap-time reductions unless EXP = NEXP, where
and
.
To overcome this obstacle, Venkatesan and
Levin [VL88] introduced a new type of
reduction using randomized algorithms.
An important application of such reductions is the result
of Impagliazzo and
Levin [IL90], who showed
that polynomial-time sampling cannot generate harder instances
than picking instances uniformly at random.