Post correspondence problem

Last updated July 30, 2024

The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946.^[1] Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.

Definition of the problem

Let $A$ be an alphabet with at least two symbols. The input of the problem consists of two finite lists $\alpha _{1},\ldots ,\alpha _{N}$ and $\beta _{1},\ldots ,\beta _{N}$ of words over $A$ . A solution to this problem is a sequence of indices $(i_{k})_{1\leq k\leq K}$ with $K\geq 1$ and $1\leq i_{k}\leq N$ for all $k$ , such that

\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 instances of the problem

Example 1

Consider the following two lists:

α₁	α₂	α₃
a	ab	bba

β₁	β₂	β₃
baa	aa	bb

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

α_i
β_i

there being an unlimited supply of each type of block. Thus the above example is viewed as

a
baa

i = 1

ab
aa

i = 2

bba
bb

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:

bba
bb

i₁ = 3

ab
aa

i₂ = 2

bba
bb

i₃ = 3

a
baa

i₄ = 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.

bb
b

1

ab
ba

2

c
bc

3

In this instance, every sequence of the form (1, 2, 2, . . ., 2, 3) is a solution (in addition to all their repetitions):

bb
b

1

ab
ba

2

ab
ba

2

ab
ba

2

c
bc

3

Proof sketch of undecidability

The most common proof for the undecidability of PCP describes an instance of PCP that can simulate the computation of an arbitrary Turing machine on a particular input. A match will occur if and only if the input would be accepted by the Turing machine. Because deciding if a Turing machine will accept an input is a basic undecidable problem, PCP cannot be decidable either. The following discussion is based on Michael Sipser's textbook Introduction to the Theory of Computation.^[2]

In more detail, the idea is that the string along the top and bottom will be a computation history of the Turing machine's computation. This means it will list a string describing the initial state, followed by a string describing the next state, and so on until it ends with a string describing an accepting state. The state strings are separated by some separator symbol (usually written #). According to the definition of a Turing machine, the full state of the machine consists of three parts:

The current contents of the tape.
The current state of the finite state machine which operates the tape head.
The current position of the tape head on the tape.

Although the tape has infinitely many cells, only some finite prefix of these will be non-blank. We write these down as part of our state. To describe the state of the finite control, we create new symbols, labelled q₁ through q_k, for each of the finite state machine's k states. We insert the correct symbol into the string describing the tape's contents at the position of the tape head, thereby indicating both the tape head's position and the current state of the finite control. For the alphabet {0,1}, a typical state might look something like:

101101110q₇00110.

A simple computation history would then look something like this:

q₀101#1q₄01#11q₂1#1q₈10.

We start out with this block, where x is the input string and q₀ is the start state:


q₀x#

The top starts out "lagging" the bottom by one state, and keeps this lag until the very end stage. Next, for each symbol a in the tape alphabet, as well as #, we have a "copy" block, which copies it unmodified from one state to the next:

a
a

We also have a block for each position transition the machine can make, showing how the tape head moves, how the finite state changes, and what happens to the surrounding symbols. For example, here the tape head is over a 0 in state 4, and then writes a 1 and moves right, changing to state 7:

q₄0
1q₇

Finally, when the top reaches an accepting state, the bottom needs a chance to finally catch up to complete the match. To allow this, we extend the computation so that once an accepting state is reached, each subsequent machine step will cause a symbol near the tape head to vanish, one at a time, until none remain. If q_f is an accepting state, we can represent this with the following transition blocks, where a is a tape alphabet symbol:

q_fa
q_f

aq_f
q_f

There are a number of details to work out, such as dealing with boundaries between states, making sure that our initial tile goes first in the match, and so on, but this shows the general idea of how a static tile puzzle can simulate a Turing machine computation.

The previous example

q₀101#1q₄01#11q₂1#1q₈10.

is represented as the following solution to the Post correspondence problem:


q₀101#

q₀1
1 q₄

0
0

1
1

#
#

1
1

q₄ 0
1 q₂

1
1

#
#

1
1

1 q₂1
q₈10

#
#

1 q₈
q₈

1
1

0
0

#
#

q₈ 1
q₈

0
0

#
#

q₈ 0
q₈

#
#

q₈

#
#

...

Variants

Many variants of PCP have been considered. One reason is that, when one tries to prove undecidability of some new problem by reducing from PCP, it often happens that the first reduction one finds is not from PCP itself but from an apparently weaker version.

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).^[3]
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,^[4] but remains undecidable for n ≥ 5. It is unknown whether the problem is decidable for 3 ≤ n ≤ 4.^[5]
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.^[6]
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.^[7] 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).^[8]
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.^[9]
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.^[10]
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.^[11]

Related Research Articles

In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules can be applied to a nonterminal symbol regardless of its context. In particular, in a context-free grammar, each production rule is of the form

In geometry, a parallelepiped is a three-dimensional figure formed by six parallelograms. By analogy, it relates to a parallelogram just as a cube relates to a square.

In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the second matrix. The resulting matrix, known as the matrix product, has the number of rows of the first and the number of columns of the second matrix. The product of matrices $A$ and $B$ is denoted as $AB$ .

In mathematics, the (field) norm is a particular mapping defined in field theory, which maps elements of a larger field into a subfield.

In linear algebra, a tridiagonal matrix is a band matrix that has nonzero elements only on the main diagonal, the subdiagonal/lower diagonal, and the supradiagonal/upper diagonal. For example, the following matrix is tridiagonal:

In linear algebra, the Frobenius companion matrix of the monic polynomial $is the square matrix defined as$

In mathematics, specifically the algebraic theory of fields, a normal basis is a special kind of basis for Galois extensions of finite degree, characterised as forming a single orbit for the Galois group. The normal basis theorem states that any finite Galois extension of fields has a normal basis. In algebraic number theory, the study of the more refined question of the existence of a normal integral basis is part of Galois module theory.

In commutative algebra and field theory, the Frobenius endomorphism is a special endomorphism of commutative rings with prime characteristic $p$ , an important class that includes finite fields. The endomorphism maps every element to its $p$ -th power. In certain contexts it is an automorphism, but this is not true in general.

In mathematics, the Smith normal form is a normal form that can be defined for any matrix with entries in a principal ideal domain (PID). The Smith normal form of a matrix is diagonal, and can be obtained from the original matrix by multiplying on the left and right by invertible square matrices. In particular, the integers are a PID, so one can always calculate the Smith normal form of an integer matrix. The Smith normal form is very useful for working with finitely generated modules over a PID, and in particular for deducing the structure of a quotient of a free module. It is named after the Irish mathematician Henry John Stephen Smith.

In mathematics, the linear algebra concept of dual basis can be applied in the context of a finite extension L/K, by using the field trace. This requires the property that the field trace Tr_L/K provides a non-degenerate quadratic form over K. This can be guaranteed if the extension is separable; it is automatically true if K is a perfect field, and hence in the cases where K is finite, or of characteristic zero.

In numerical analysis, the Crank–Nicolson method is a finite difference method used for numerically solving the heat equation and similar partial differential equations. It is a second-order method in time. It is implicit in time, can be written as an implicit Runge–Kutta method, and it is numerically stable. The method was developed by John Crank and Phyllis Nicolson in the 1940s.

In the mathematical field of set theory, ordinal arithmetic describes the three usual operations on ordinal numbers: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an explicit well-ordered set that represents the result of the operation or by using transfinite recursion. Cantor normal form provides a standardized way of writing ordinals. In addition to these usual ordinal operations, there are also the "natural" arithmetic of ordinals and the nimber operations.

In mathematics, the resultant of two polynomials is a polynomial expression of their coefficients that is equal to zero if and only if the polynomials have a common root, or, equivalently, a common factor. In some older texts, the resultant is also called the eliminant.

Conjunctive grammars are a class of formal grammars studied in formal language theory. They extend the basic type of grammars, the context-free grammars, with a conjunction operation. Besides explicit conjunction, conjunctive grammars allow implicit disjunction represented by multiple rules for a single nonterminal symbol, which is the only logical connective expressible in context-free grammars. Conjunction can be used, in particular, to specify intersection of languages. A further extension of conjunctive grammars known as Boolean grammars additionally allows explicit negation.

The Hückel method or Hückel molecular orbital theory, proposed by Erich Hückel in 1930, is a simple method for calculating molecular orbitals as linear combinations of atomic orbitals. The theory predicts the molecular orbitals for π-electrons in π-delocalized molecules, such as ethylene, benzene, butadiene, and pyridine. It provides the theoretical basis for Hückel's rule that cyclic, planar molecules or ions with $π-electrons are aromatic. It was later extended to conjugated molecules such as pyridine, pyrrole and furan that contain atoms other than carbon and hydrogen (heteroatoms). A more dramatic extension of the method to include σ-electrons, known as the extended Hückel method (EHM), was developed by Roald Hoffmann. The extended Hückel method gives some degree of quantitative accuracy for organic molecules in general and was used to provide computational justification for the Woodward-Hoffmann rules. To distinguish the original approach from Hoffmann's extension, the Hückel method is also known as the simple Hückel method (SHM).$

In automata theory, the class of unrestricted grammars is the most general class of grammars in the Chomsky hierarchy. No restrictions are made on the productions of an unrestricted grammar, other than each of their left-hand sides being non-empty. This grammar class can generate arbitrary recursively enumerable languages.

In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of automata may be defined, including measure-once and measure-many automata. Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. QFAs are, in turn, special cases of geometric finite automata or topological finite automata.

A Riemann problem, named after Bernhard Riemann, is a specific initial value problem composed of a conservation equation together with piecewise constant initial data which has a single discontinuity in the domain of interest. The Riemann problem is very useful for the understanding of equations like Euler conservation equations because all properties, such as shocks and rarefaction waves, appear as characteristics in the solution. It also gives an exact solution to some complex nonlinear equations, such as the Euler equations.

In mathematics, the discrete Fourier transform over a ring generalizes the discrete Fourier transform (DFT), of a function whose values are commonly complex numbers, over an arbitrary ring.

The cyclotomic fast Fourier transform is a type of fast Fourier transform algorithm over finite fields. This algorithm first decomposes a DFT into several circular convolutions, and then derives the DFT results from the circular convolution results. When applied to a DFT over $, this algorithm has a very low multiplicative complexity. In practice, since there usually exist efficient algorithms for circular convolutions with specific lengths, this algorithm is very efficient.$

References

↑ E. L. Post (1946). "A variant of a recursively unsolvable problem" (PDF). Bull. Amer. Math. Soc. 52 (4): 264–269. doi:10.1090/s0002-9904-1946-08555-9. S2CID 122948861.
↑ Michael Sipser (2005). "A Simple Undecidable Problem". Introduction to the Theory of Computation (2nd ed.). Thomson Course Technology. pp. 199–205. ISBN 0-534-95097-3.
↑ Salomaa, Arto (1981). Jewels of Formal Language Theory. Pitman Publishing. pp. 74–75. ISBN 0-273-08522-0. Zbl 0487.68064.
↑ Ehrenfeucht, A.; Karhumäki, J.; Rozenberg, G. (November 1982). "The (generalized) post correspondence problem with lists consisting of two words is decidable". Theoretical Computer Science . 21 (2): 119–144. doi:10.1016/0304-3975(89)90080-7.
↑ T. Neary (2015). "Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words". In Ernst W. Mayr and Nicolas Ollinger (ed.). 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). STACS 2015. Vol. 30. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 649–661. doi: 10.4230/LIPIcs.STACS.2015.649 .
↑ K. Ruohonen (1983). "On some variants of Post's correspondence problem". Acta Informatica . 19 (4). Springer: 357–367. doi:10.1007/BF00290732. S2CID 20637902.
↑ Michael R. Garey; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . W.H. Freeman. p. 228. ISBN 0-7167-1045-5.
↑ Y. Gurevich (1991). "Average case completeness" (PDF). J. Comput. Syst. Sci. 42 (3). Elsevier Science: 346–398. doi:10.1016/0022-0000(91)90007-R. hdl:2027.42/29307.
↑ V. Halava; M. Hirvensalo; R. de Wolf (2001). "Marked PCP is decidable". Theor. Comput. Sci. 255 (1–2). Elsevier Science: 193–204. doi:10.1016/S0304-3975(99)00163-2.
↑ P. Chambart; Ph. Schnoebelen (2007). Post embedding problem is not primitive recursive, with applications to channel systems (PDF). Lecture Notes in Computer Science. Vol. 4855. Springer. pp. 265–276. doi:10.1007/978-3-540-77050-3_22. ISBN 978-3-540-77049-7.
↑ Paul C. Bell; Igor Potapov (2010). "On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix Semigroups". International Journal of Foundations of Computer Science. 21 (6). World Scientific: 963–978. arXiv: 0902.1975 . doi:10.1142/S0129054110007660.

External links

Eitan M. Gurari. An Introduction to the Theory of Computation, Chapter 4, Post's Correspondence Problem. A proof of the undecidability of PCP based on Chomsky type-0 grammars.
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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Post46-1] E. L. Post (1946). "A variant of a recursively unsolvable problem" (PDF). Bull. Amer. Math. Soc. 52 (4): 264–269. doi:10.1090/s0002-9904-1946-08555-9. S2CID 122948861.

[sipser05-2] Michael Sipser (2005). "A Simple Undecidable Problem". Introduction to the Theory of Computation (2nd ed.). Thomson Course Technology. pp. 199–205. ISBN 0-534-95097-3.

[3] Salomaa, Arto (1981). Jewels of Formal Language Theory. Pitman Publishing. pp. 74–75. ISBN 0-273-08522-0. Zbl 0487.68064.

[EKR82-4] Ehrenfeucht, A.; Karhumäki, J.; Rozenberg, G. (November 1982). "The (generalized) post correspondence problem with lists consisting of two words is decidable". Theoretical Computer Science . 21 (2): 119–144. doi:10.1016/0304-3975(89)90080-7.

[N15-5] T. Neary (2015). "Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words". In Ernst W. Mayr and Nicolas Ollinger (ed.). 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). STACS 2015. Vol. 30. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 649–661. doi: 10.4230/LIPIcs.STACS.2015.649 .

[Ruohonen83-6] K. Ruohonen (1983). "On some variants of Post's correspondence problem". Acta Informatica . 19 (4). Springer: 357–367. doi:10.1007/BF00290732. S2CID 20637902.

[GJ79-7] Michael R. Garey; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . W.H. Freeman. p. 228. ISBN 0-7167-1045-5.

[Gurevich91-8] Y. Gurevich (1991). "Average case completeness" (PDF). J. Comput. Syst. Sci. 42 (3). Elsevier Science: 346–398. doi:10.1016/0022-0000(91)90007-R. hdl:2027.42/29307.

[HHW01-9] V. Halava; M. Hirvensalo; R. de Wolf (2001). "Marked PCP is decidable". Theor. Comput. Sci. 255 (1–2). Elsevier Science: 193–204. doi:10.1016/S0304-3975(99)00163-2.

[CS07-10] P. Chambart; Ph. Schnoebelen (2007). Post embedding problem is not primitive recursive, with applications to channel systems (PDF). Lecture Notes in Computer Science. Vol. 4855. Springer. pp. 265–276. doi:10.1007/978-3-540-77050-3_22. ISBN 978-3-540-77049-7.

[BP10-11] Paul C. Bell; Igor Potapov (2010). "On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix Semigroups". International Journal of Foundations of Computer Science. 21 (6). World Scientific: 963–978. arXiv: 0902.1975 . doi:10.1142/S0129054110007660.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]