The Post correspondence problem was first studied by Post
(see, for example, [Dav77]),
which is to decide, when given
a nonempty list
of pairs of binary strings, whether there is
a sequence of integers
, with 
, such that
.
The sequence
is called a solution of length 
to this
instance.
DISTRIBUTIONAL POST CORRESPONDENCE PROBLEM
Instance. A nonempty list
of pairs of
binary strings, and a positive integer 
.
The size of the instance is 
.
Question. Is there a solution to 
of length at most ?
Distribution. Randomly and independently choose positive integers
and 
, then randomly and independently choose binary strings
. The random choices are made with respect to the
default uniform
probability distributions on positive integers and binary
strings. Hence, the probability distribution 
is proportional to
The distributional Post correspondence problem was shown to be average-case NP-complete by Gurevich [Gur91].
By a slight modification of the distributional
Post correspondence problem, Gurevich [Gur90] (see also [BG95])
defined the following correspondence problem for strings and showed
that it is average-case NP-complete.
DISTRIBUTIONAL STRING CORRESPONDENCE PROBLEM
Instance. A binary string 
, a nonempty list
of binary string pairs,
and a positive integer .
The size of the instance is 
.
Question. Are there strings 
and 
, 
, such that 
?
Distribution. Proportional to 
.
DISTRIBUTIONAL PALINDROME PROBLEM
Instance. A context-free grammar with productions
and a positive integer , where
and 
are binary strings, and 
is
the empty string.
The size of the instance is .
Question. Can a nonempty palindrome string
be derived within steps?
Distribution. Randomly and independently choose
positive integers and , then randomly and
independently choose binary strings 
with respect to the default uniform distributions.
Let 
, then
the probability distribution of an palindrome instance is the same
as .
The distributional palindrome problem was shown to be average-case NP-complete by Gurevich [Gur91].
