Post correspondence problem

undecidable decision problem

Uses your system voice; voice and rate in settings.

Q798572Snapshot

≈ 7 min read

Names in other languages

  • Españolproblema de correspondencia de Post
  • PortuguêsProblema da correspondência de Post
  • FrançaisProblème de correspondance de Post
  • DeutschPostsches Korrespondenzproblem
  • ČeštinaPostův korespondenční problém
  • PolskiProblem odpowiedniości Posta
  • EnglishPost correspondence problem
  • isSamræmingarverkefni Posts
  • עבריתבעיית ההתאמה של פוסט

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability. \alpha_{i_1} \ldots \alpha_{i_K} = \beta_{i_1} \ldots \beta_{i_K}. The decision problem then is to decide whether such a solution exists or not.

Alternative definition

g: (i_1,\ldots,i_K) \mapsto \alpha_{i_1} \ldots \alpha_{i_K} h: (i_1,\ldots,i_K) \mapsto \beta_{i_1} \ldots \beta_{i_K}. This gives rise to an equivalent alternative definition often found in the literature, according to which any two homomorphisms g,h with a common domain and a common codomain form an instance of the Post correspondence problem, which now asks whether there exists a nonempty word w in the domain such that g(w)=h(w) . Another definition describes this problem easily as a type of puzzle.

We begin with a collection of dominos, each containing two strings, one on each side. An individual domino looks like \begin{bmatrix}a \\ ab\end{bmatrix} and a collection of dominos looks like { \begin{bmatrix}bc \\ ca\end{bmatrix}, \begin{bmatrix}a \\ ab\end{bmatrix}, \begin{bmatrix}ca \\ a\end{bmatrix}, \begin{bmatrix}abc \\ c\end{bmatrix} } .

The task is to make a list of these dominos (repetition permitted) so that the string we get by reading off the symbols on the top is the same as the string of symbols on the bottom. This list is called a match. The Post correspondence problem is to determine whether a collection of dominos has a match.

For example, the following list is a match for this puzzle. { \begin{bmatrix}a \\ ab\end{bmatrix}, \begin{bmatrix}bc \\ ca\end{bmatrix}, \begin{bmatrix}a \\ ab\end{bmatrix}, \begin{bmatrix}abc \\ c\end{bmatrix} } . For some collections of dominos, finding a match may not be possible.

For example, the collection { \begin{bmatrix}abc \\ ab\end{bmatrix}, \begin{bmatrix}ca \\ a\end{bmatrix}, \begin{bmatrix}acc \\ ba\end{bmatrix} } . cannot contain a match because every top string is longer than the corresponding bottom string.

Example 1

Consider the following two lists: A solution to this problem would be the sequence (3, 2, 3, 1), because \alpha_3 \alpha_2 \alpha_3 \alpha_1 = bba \cdot ab \cdot bba \cdot a = bbaabbbaa = bb \cdot aa \cdot bb \cdot baa = \beta_{3} \beta_{2} \beta_{3} \beta_{1}. Furthermore, since (3, 2, 3, 1) is a solution, so are all of its "repetitions", such as (3, 2, 3, 1, 3, 2, 3, 1), etc.; that is, when a solution exists, there are infinitely many solutions of this repetitive kind.

However, if the two lists had consisted of only \alpha_2, \alpha_3 and \beta_{2}, \beta_{3} from those sets, then there would have been no solution (the last letter of any such α string is not the same as the letter before it, whereas β only constructs pairs of the same letter). A convenient way to view an instance of a Post correspondence problem is as a collection of blocks of the form there being an unlimited supply of each type of block.

Thus the above example is viewed as i = 1 i = 2 i = 3 where the solver has an endless supply of each of these three block types. A solution corresponds to some way of laying blocks next to each other so that the string in the top cells corresponds to the string in the bottom cells. Then the solution to the above example corresponds to: i 1 = 3 i 2 = 2 i 3 = 3 i 4 = 1

Example 2

Again using blocks to represent an instance of the problem, the following is an example that has infinitely many solutions in addition to the kind obtained by merely "repeating" a solution. 1 2 3 In this instance, every sequence of the form (1, 2, 2, . . ., 2, 3) is a solution (in addition to all their repetitions): 1 2 2 2 3 The problem may be phrased in terms of monoid morphisms f, g from the free monoid B ∗ to the free monoid A ∗ where B is of size n. The problem is to determine whether there is a word w in B + such that f(w) = g(w). The condition that the alphabet A have at least two symbols is required since the problem is decidable if A has only one symbol.

A simple variant is to fix n, the number of tiles. This problem is decidable if n ≤ 2, but remains undecidable for n ≥ 5. It is unknown whether the problem is decidable for 3 ≤ n ≤ 4.

The circular Post correspondence problem asks whether indexes i_1, i_2,\ldots can be found such that \alpha_{i_1} \cdots \alpha_{i_k} and \beta_{i_1} \cdots \beta_{i_k} are conjugate words, i.e., they are equal modulo rotation. This variant is undecidable.

One of the most important variants of PCP is the bounded Post correspondence problem, which asks if we can find a match using no more than k tiles, including repeated tiles. A brute force search solves the problem in time O(2 k ), but this may be difficult to improve upon, since the problem is NP-complete.

Unlike some NP-complete problems like the boolean satisfiability problem, a small variation of the bounded problem was also shown to be complete for RNP, which means that it remains hard even if the inputs are chosen at random (it is hard on average over uniformly distributed inputs). Another variant of PCP is called the marked Post Correspondence Problem, in which each \alpha_i must begin with a different symbol, and each \beta_i must also begin with a different symbol.

Halava, Hirvensalo, and de Wolf showed that this variation is decidable in exponential time. Moreover, they showed that if this requirement is slightly loosened so that only one of the first two characters need to differ (the so-called 2-marked Post Correspondence Problem), the problem becomes undecidable again.

The symmetric Post Correspondence Problem adds the additional restriction that for each pair (\alpha_i, \beta_i) , a pair (\beta_i, \alpha_i) = (\alpha_j, \beta_j) is also present. This variant is undecidable.

The Post Embedding Problem is another variant where one looks for indexes i_1, i_2, \ldots such that \alpha_{i_1} \cdots \alpha_{i_k} is a (scattered) subword of \beta_{i_1} \cdots \beta_{i_k} . This variant is easily decidable since, when some solutions exist, in particular a length-one solution exists.

More interesting is the Regular Post Embedding Problem, a further variant where one looks for solutions that belong to a given regular language (submitted, e.g., under the form of a regular expression on the set \{1,\ldots,N\} ). The Regular Post Embedding Problem is still decidable but, because of the added regular constraint, it has a very high complexity that dominates every multiply recursive function.

The Identity Correspondence Problem (ICP) asks whether a finite set of pairs of words (over a group alphabet) can generate an identity pair by a sequence of concatenations. The problem is undecidable and equivalent to the following Group Problem: is the semigroup generated by a finite set of pairs of words (over a group alphabet) a group.

The problem has been studied in the context of groups, using a similar phrasing to the monoid morphism language. Post's Correspondence Problem for Groups takes as input a pair of group homomorphisms f, g: F(B)\to G from the free group F(B) to the group G , and tries to determine whether there is a word w in F(B) such that f(w) = g(w)\neq1 .

It is known to be decidable when G is a virtually nilpotent group, and undecidable for G a hyperbolic group. The analogue of the marked Post Correspondence Problem is also known to be decidable for groups. Dong, Jing.

"The Analysis and Solution of a PCP Instance." 2012 National Conference on Information Technology and Computer Science. The paper describes a heuristic rule for solving some specific PCP instances.

Online PHP Based PCP Solver PCP AT HOME PCP - a nice problem PCP solver in Java Post Correspondence Problem

Text derived from https://en.wikipedia.org/w/index.php?oldid=1361182568 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot post-correspondence-problem-091579-6007b49d0c8bd14c · hash 6007b49d0c8bd14ccbad2a5a4295a7b020d082e29173a28692fd7035e463f454 · captured 2026-06-26 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Post correspondence problem”, snapshot post-correspondence-problem-091579-6007b49d0c8bd14c. https://encyclopegia.org/a/post-correspondence-problem

Sources cited in this revision

6 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.