A tile is a square with a symbol on each side which may not be rotated
or turned over.
We assume that there are infinite copies of each tile.
By a tiling of an 
square it means an arrangement of
tiles covering the square in which the symbols
on the common sides of adjacent tiles are the same.
The size of a tile is the length of the binary representation of
the four symbols at each edge in a fixed order.
DISTRIBUTIONAL TILING PROBLEM
Instance.
A finite set of tiles 
, a positive integer 
, and
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 size of the instance is plus the sum of
the sizes of all members in plus the sum of the sizes
of all members in 
.
Question. Can be extended to
tile an square using tiles from ?
Distribution.
Proportional to
, where 
is the probability of (one
can use one's favorite distribution to select or simply
select one uniformly at random among binary strings since is
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 
.
Levin [Lev86] originally considered the distributional tiling
problem for tiles with marked corners, namely,
the corners of tiles, instead of edges, are marked
with letters. In the tiling
of an square, letters on the touching corners
of adjacent tiles are the same.
The distributional tiling problem for tiles with marked corners was shown to be average-case NP-complete by Levin [Lev86], but only a proof sketch was given. A detailed proof for tiles with marked edges was given in [Gur91] (see also [BW93][WB95]).