Denote by DistNP the class of all distributional NP problems
such that
for some p-time computable distribution 
.
Other names such as RNP [Gur91a],
NP, P-comp
e[BCGL92], and
DNP [WB93a] have
also been used for DistNP. DistNP
was first used in [BCGL92][IL90].
A distributional
problem is average-case NP-complete (or complete for
DistNP) if it is in DistNP and every distributional problem
in DistNP is reducible to it. Levin [Lev86] showed that a distributional tiling problem
is average-case NP-complete. Levin also implicitly
showed that a distributional halting problem
is average-case NP-complete.
Gurevich [Gur91a] explicitly defined such
a problem and provided a simple proof of its completeness.
Let 
be a fixed enumeration of
nondeterministic Turing machines in which the index
is an integer in binary form that codes the symbols, states, and
transition table of the th Turing machine 
.
The DISTRIBUTIONAL HALTING PROBLEM (VERSION 1)
consists of binary
strings , 
, and 
as instances, where and <
IMG ALIGN=BOTTOM SRC="_22185_tex2html_wrap3895.gif"> are
integers. The question is to decide whether
accepts within 
steps.
Denote by 
the set of all positive instances.
The probability distribution 
of instance 
(positive or negative) is proportional to
, where 
and 
.
The halting problem is then denoted by DH1 = 
.
Proof. be an arbitrary problem in DistNP. Then
there is a nondeterministic
Turing machine 
that accepts 
in polynomial time.
By the Distribution Controlling Lemma, there is a total, one-one,
p-time computable and
invertible function 
such that 
.
Define a Turing machine 
as follows. On input 
,
if 
is defined, then
simulates on 
and rejects otherwise.
Clearly, for all ,
accepts iff accepts 
.
It is easy to see that on input 
is bounded in time
for some polynomial 
.
Let be an index such that 
. Let
.
Then 
is one-one and p-time computable.
By construction, 
iff 
.
Moreover, 
for some polynomial 
,
which dominates 
. So 
.
The distributional tiling problem was first shown to be complete
by Levin in [Lev86] and a detailed proof
can be found in [Gur91a]
[BW93].
A tile is a square with a symbol on each side that may not be rotated
or turned over.
We assume that there are an infinite supply of copies of each tile.
By a tiling of an 
square we mean an arrangement of
tiles covering the square in which the symbols
on the common sides of adjacent tiles are the same.
The DISTRIBUTIONAL TILING PROBLEM (DT) consists of
binary strings
, , and 
as instances, where is a finite s
et
of tiles, is an integer, and
(
) is a sequence
of tiles that match each other, i.e., the
symbol on the right side of
is the same as that on the left side of 
.
The question is to decide whether can be extended to
tile an square using tiles from .
Denote by BT the set of all positive instances 
.
The probability distribution 
on instance
(positive or negative) is proportional to
, where 
is the probability of (one
can use one's favorite distribution to select or can simply
select uniformly at random among binary strings since can
be coded in binary) and
is the probability of choosing , where is chosen by
choosing 
at random with
probability 
, choosing the first tile 
at random from ,
and choosing the (
) sequentially and uniformly at random
from those tiles in that match 
.
Let 
and let
be as in the proof of Theorem 3.4.
Let 
.
Similarly to the proof of Theorem 3.4 and
the standard completeness proof for bounded tiling in the worst case,
one might be tempted
to reduce to DT by reducing an instance of to an
instance of DT in which represents the initial instantaneous
description of an appropriate Turing machine
on 
followed by some ``blank'' tiles. The problem with this
approach is that , which is at most 
,
is too small to
dominate . If does not end with ``blank'' tiles,
then could be dominated
by 
. However, something needs to be done to make sure that
reductions will not reduce a negative instance of to a
positive instance of DT.
Proof Sketch. and let 
be as in the
proof of Theorem 3.4. Let be a nondeterministic
Turing machine that accepts . Assume that the length of
every computation path of on input is
bounded by a polynomial in 
. For any string ,
let 
be 
written in binary.
Set 
. Then
and
can be found efficiently from
any string beginning with 
.
Construct a Turing machine as follows.
It rejects any input if the input does not begin with for some ,
or 
is not defined.
then simulates on 
.
Let 
. Then
will either accept all
inputs beginning
with 
or will reject all
inputs beginning
with
(depending on whether or not accepts ),
and there exists a polynomial such that the length of
every computation path
of on is strictly less than .
Following a standard procedure (e.g., see [LP81]), we can
construct tiles to represent the transition function of ,
and we can construct tiles
that can duplicate tape symbols 
and pairs 
in the vertical direction,
where is the accepting state.
We then construct tiles
and 
for 
,
where 
represents the symbols on each side
of a tile in the order of top, bottom, left, and right,
is the initial state of , and $ and # are symbols that
have not been used by other tiles. Let 
be the set of all
these tiles. Let 
, where
and 
represents the th bit of
. The probability of the th tile of for
is 
since there are only two tiles
that can match the 
st tile. Since
and 
,
is proportional to
and so
. It is easy to see
that iff 
with occupying the
bottom left-hand side of the 
square, since
the tiling can only duplicate the computation path, which
can be extended to cover the entire square only when an accepting state
is reached.
Several more natural NP-complete problems such as the Post correspondence problem [Gur91a], the word problem for Thue systems [WB95], and the word problem for finitely presented groups [Wan95a] have also been shown to be complete for DistNP using p-time reductions in which each parameter of the instance is selected uniformly at random. Proofs of these results are more involved and are not included here due to space limitations.
