The distributional tiling problem was the first problem known to be average-case NP-complete, which was shown by Levin [Lev86]. Gurevich provided a more accessible proof with all the details [Gur91]. The proof presented here is from [BW93].
Denote by BT the set of all positive instances 
of the
tiling problem
and 
the probability distribution on instance
(positive or negative).
The idea of the proof is as follow.
Let 
and let
be as in the proof of Theorem 4.1.
Let 
.
One might be tempted
to reduce 
to 
by
reducing an instance 
of 
to an
instance , where 
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 
. But something needs to be done to make sure that
reductions will not reduce a negative instance of to a
positive instance of BT. This is done by a careful coding
method. We first consider tiles with marked edges.
Proof.. It follows that
there is
a (non-deterministic) Turing machine 
that accepts
in polynomial time.
Without loss of generality, we assume that all the computation paths of
are bounded by a polynomial of input length.
By the Distribution Controlling Lemma, there is a total, one-one,
p-time computable and p-time invertible function 
such that
for all ,
.
We would like a Turing machine to be able to find the string 
inside a longer string. This can be done in the following way: for
any string 
, let
be 
written in binary.
Set 
. Then given a string which has
as a prefix, 
can count the number of 0's before the initial 1,
use this number to find the number , and then use to find
. Notice that
.
Let be a Turing machine which, given an input 
beginning with ,
determines as above.
(We can assume that if does not begin with a 0 or that if a cannot
be determined because is too short, then rejects .)
then determines whether 
for some .
This
can be done in time polynomial in 
.
If so, then simulates on , otherwise rej
ects.
For convenience, let 
.
Notice that for any given ,
will either accept all or reject all inputs beginning
with 
(depending on whether or not accepts ),
and all the computation paths
of will be less than 
for some polynomial 
.
For simplicity, we say that accepts or rejects .
The fact that ignores any input after is important in
the construction of our reduction. Clearly, accepts iff
accepts .
Let 
be the set of states of ,
with 
the initial state of ,
the accepting state,
and 
the rejecting state.
Let 
be the transition function of , and 
be the blank
symbol.
Let 
consist of the following legal tiles:
for 
for 
,
:
for 
,
:
for 
:
and for 
:
The desired reduction is defined by
,
where if
is written
for 
,
consists of the tiles:
Note that the probability of the 
th tile of
for 
is 1/2.
Clearly, 
is one-one and p-time computable.
If extends to a set of legal tiles which tile a 
square, then will have to occupy the bottom left hand side of the
square. In this case, the symbols at the top of the
bottom row will represent the initial ID of on some input beginning
with , and the symbols at the top of the
th row from the bottom will represent the
ID of a position reachable by within steps.
Since will reach the
accepting or rejecting state in less than steps, and the tiling can
only duplicate the accepting state, can extend to a tiling only if
accepts , which happens exactly when accepts .
Similarly, if
accepts ,
then can be extended to a tiling of a
square.
We now verify that the reduction satisfies the domination requirement.
To see this, we note that
,
which is proportional to
for some polynomial 
. Hence,
. It follows by
Lemma 2.1 that 
.
It is easy to modify the above completeness proof
to show that
the distributional tiling problem with marked corners is also
complete for DistNP.
We do so by constructing tiles such that a tile letter represents
a cell in an ID of that either encodes an input
symbol and the direction to the head, or encodes a state of the head
and the direction of the cell that the head looks at. Hence, there
are only two different tiles that can be chosen for the initial
sequence of tiles after the first tile was selected, and so the
domination property is satisfied.
