All the reductions we have studied so far are variants of many-one reductions. Other types of reductions such as truth-table reductions and Turing reductions can be similarly defined for distributional problems. The reader should find no difficulty in defining them with the desired properties. It is a long-standing open problem whether Turing reductions (or truth-table reductions) are provably more powerful than many-one reductions on NP problems. Not much has been done for distributional NP problems. However, it is not known whether truth-table or Turing reductions can help identify additional average-case NP-complete problems encountered in practice. For one thing, we note that all the known natural NP-complete problems are indeed many-one complete. Nevertheless, NP search problems can be reduced to NP decision problems by Turing reductions. For distributional problems, randomized truth-table reductions (defined below) are sufficient [BCGL92].
By Theorem 4.3, an ap-time randomized algorithm that
produces a correct output with probability at least 
can be
iterated to get a correct output with probability 1.
We also note that Theorem 4.1 remains true if one uses
deterministic Turing reductions [Gur91a].
If in a p-time (ap-time) randomized Turing reduction
all queries can be generated at the beginning
independent of other queries,
then the reduction is called a p-time (ap-time)
randomized truth-table
reduction. Randomized Turing reductions are closed for randomized ap-time
solvable problems and are transitive in the special case where on
input 
only queries of length at least 
are asked, for
a constant 
[BCGL92].
As pointed out in [BCGL92], the standard
Turing reduction
of a search problem to the corresponding decision problem,
which asks queries to the set of prefixes of
a solution on input , fails on domination when the query string
is too long. This is because has distribution
with input distribution 
, which will
be too small to dominate 
when 
is large.
However, if the search problem has
a unique solution, then instead of asking for
prefixes of a solution, one can ask non-adaptively and
deterministically for the 
th bit of
the solution with probability 
. The domination
condition is therefore satisfied. Based on this idea,
Ben-David et al. [BCGL92] obtained the following result.
Proof Sketch.simplicity, assume that 
implies 
. Let
, and let
be a set of standard
universal hash functions from
strings of length 
to strings of length 
(e.g., 
matrices over the finite field 
).
Define 
as follows.
An instance will be a binary string and an integer , and
an instance will be in if there exists
a 
such that
, , 
, 
, and the 
th bit of is 1.
The distribution
is defined by 
if
and 
;
and 0 otherwise.
Construct a truth-table reduction 
as follows.
On input , for every
value of 
, first
selects uniformly at random
an 
in and a 
of length .
Let 
. then makes queries
, and 
to and
outputs 
.
Clearly, runs in time polynomial in .
To check the validity,
let 
and assume 
(the case
that 
is straightforward). Let
if
and
otherwise.
Then 
.
It follows that for a randomly selected and
of length , the
expected number of satisfying 
is between
and 
. By Markov's inequality
and the property of universal
hashing that pairs of hashing points are pairwise independent,
the probability that there is a unique such that
is great than or equal
to for some constant . In such
a case returns a correct answer .
To check the domination condition, it suffices to note that
appears as a query with probability
.
