Definition:   Given an alphabet S, one instance of Post's correspondence problem of size s is a finite set of pairs of strings (g_i , h_i) ( i = 1...s s>=1) over the alphabet S.  A solution of length n >= 1 to this instance is a sequence i₁ i₂ ... i_n of selections such that the strings g_i1g_i2 ... g_in and h_i1h_i2 ... h_in formed by concatenation are identical.

Width of a PCP instance is the length of the longest string in g_i and h_i (i = 1, 2, ... , s). Pair i is the short name for pair (g_i , h_i), where g_i and h_i are the top string and bottom string of the pair respectively. Mostly, people are interested in optimal solution, which has the shortest length over all possible solutions to an instance. The corresponding length is called optimal length. We use the word hard or difficult to describe instances whose optimal lengths are very large. For simplicity, we restrict the alphabet S to {0, 1}, and it is easy to transform other alphabets to their equivalent binary format.

To describe subclasses of Post’s Correspondence Problem, we use PCP[s] to represent the set of all PCP instances of size s, and PCP[s, w] the set of all PCP instances of size s and width w.

For convenience, we use a matrix of 2 rows and s columns to represent instances of PCP[s], where string g_i is located at (i , 1) and h_i at (i , 2). The following is the matrix representation of the instance {{100, 1}, {0, 100}, {1, 00}} in PCP[3,3].

After the elimination of blanks and concatenation of strings in the top and bottom separately, it turns to:

Now, the string in the top is identical to the one in the bottom; therefore, these selections form a solution to PCP (1). When all combinations of up to 7 selections of pairs are tested, this solution is thus proven to be the unique optimal solution to this instance.

PCP's theoretical place
Post's correspondence problem was first raised by Post in 1946 as undecidable problem [1]. It is frequently used in the literature as a basis to prove the undecidabily of other problems. The problem of size 2 has been proved decidable [2]. Some researchers in Finland found a simpler proof [3]. The problem of size 7 has been proved undecidable [4]. Now the decidablility of problems with size between 3 and 6 is still pending.

[1] Post, E., L., A variant of a recursively unsolvable problem,Bull. of the Am. Math. Soc., 52, 1946.
[2] Ehrenfeucht, A., Karhumaki, J. and Rozenberg, G., The (generalized) post correspondece problem with lists consisting of two words is decidable, Theoret. Comput. Sci.,21, 2,1982.
[3] Vesa Halava, Tero Harju and Mika Hirvensalo, Binary (Generalized) Post Correspondence Problem, TUCS Technical Report No. 357, August 2000. [PS file]
[4] Y. Matiyasevich and G.Senizergues, Decision problems for semi-Thue systems with a few rules, Proceedings, 11th Anual IEEE Symposium on Logic in Computer Science, 1996. [PS file]

You are the No. visitor to this webpage since May 5, 2001
Last modified on April 25, 2003 by Ling Zhao