Post correspondence problem

The Postsche correspondence problem (after Emil Leon Post , abbreviated PKP or English PCP ) is an example of an undecidable problem in theoretical computer science . It is often used to show the undecidability of other problems by means of reduction .

Given is a finite sequence of pairs of non-empty words over a finite alphabet. One also calls a problem case or an instance . ${\displaystyle P}$ ${\displaystyle \left((x_{1},y_{1}),(x_{2},y_{2}),\ldots ,(x_{m},y_{m})\right)}$ ${\displaystyle x_{1},x_{2},\ldots ,x_{m},y_{1},y_{2},\ldots ,y_{m}}$ ${\displaystyle P}$

A non-empty sequence of indices is a solution to the problem if the concatenation (concatenation) of the words is equal to the concatenation of the words . ${\displaystyle I=i_{1},i_{2},\ldots ,i_{n}}$ ${\displaystyle \{1,2,\ldots ,m\}}$ ${\displaystyle P}$ ${\displaystyle \left.{x_{i_{1}},x_{i_{2}},\ldots ,x_{i_{n}}}\right.}$ ${\displaystyle \left.{y_{i_{1}},y_{i_{2}},\ldots ,y_{i_{n}}}\right.}$

The correspondence problem is then the task of specifying for any problem case whether it has a solution or not. The correspondence problem is undecidable , that is, there is no algorithm that gives the correct answer to any given problem.

Illustrative representation

The word pairs in a problem case can be thought of as dominoes with one half and the other half . There are types of dominoes and any number of dominoes of each type are available. ${\displaystyle (x_{i},y_{i})}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{i}}$ ${\displaystyle m}$

The correspondence problem can now be understood as follows: Is there a sequence of dominoes such that the words on the upper half of the dominoes (read from left to right) result in the same word as the words (read from left to right) from the lower half of the folded dominoes?

example

Given:

${\displaystyle P_{1}=\left((1,101),(10,00),(011,11)\right)}$

${\displaystyle \left.x_{1}=1\right.,}$ ${\displaystyle \left.x_{2}=10\right.,}$ ${\displaystyle \left.x_{3}=011\right.}$
${\displaystyle \left.y_{1}=101\right.,}$ ${\displaystyle \left.y_{2}=00\right.,}$ ${\displaystyle \left.y_{3}=11\right.}$

Solution:

${\displaystyle I_{1}=\left(1,3,2,3\right)}$

The following applies: . ${\displaystyle x_{1}\cdot x_{3}\cdot x_{2}\cdot x_{3}=1\cdot 011\cdot 10\cdot 011=101110011=101\cdot 11\cdot 00\cdot 11=y_{1}\cdot y_{3}\cdot y_{2}\cdot y_{3}}$

${\displaystyle I_{1}}$is therefore a solution to the problem . ${\displaystyle P_{1}}$

As Domino consequence . ${\displaystyle {\frac {1}{101}}\ {\frac {011}{11}}\ {\frac {10}{00}}\ {\frac {011}{11}}}$

Comments on this:

Of course, every concatenation of two solutions or a solution with itself forms a solution again. So one can ask whether a solution is made up of shorter solutions. The solution is not made up of shorter solutions: it is primitive. Sometimes there are several primitive solutions, but not in this example. ${\displaystyle \left(1,3,2,3\right)}$

The example might give the impression that Post's correspondence problem is not that difficult after all. However, there are also problem cases that only have very long solutions. ${\displaystyle P_{1}}$

Here is an example ${\displaystyle P_{2}}$

${\displaystyle \left.x_{1}=001\right.,}$ ${\displaystyle \left.x_{2}=01\right.,}$ ${\displaystyle \left.x_{3}=01\right.,}$ ${\displaystyle \left.x_{4}=10\right.}$
${\displaystyle \left.y_{1}=0\right.,}$ ${\displaystyle \left.y_{2}=011\right.,}$ ${\displaystyle \left.y_{3}=101\right.,}$ ${\displaystyle \left.y_{4}=001\right.}$

A shortest solution already consists of 66 pairs:

${\displaystyle I_{1}=(2,4,3,4,4,2,1,2,4,3,4,3,4,4,3,4,4,2,1,4,4,2,1,3,4,1,1,3,4,4,4,2,1,2,1,1,1,3,4,3,4,1,2,1,4,4,2,1,4,1,1,3,4,1,1,3,1,1,3,1,2,1,4,1,1,3)}$

From this solution one can easily see the complexity of the problem.

Boundaries between decidability and undecidability

A solution can be found after a finite amount of time through systematic trial and error, if there is one. The PKP is thus a semi-decidable problem. However, if there is no solution, this algorithm will not terminate . Proof that there is no decision-making process for PKP can be provided by reducing the stopping problem to a variant of the correspondence problem .

special cases

Limiting the alphabet makes the problem “easier”.

If you only allow word pairs over a single-element alphabet, then the PKP becomes a decidable problem. The PKP restricted to a two-element alphabet, however, remains undecidable, because any alphabet can be coded in a two-element alphabet.

You can also limit the size, i.e. the number of pairs in problem cases . For sizes 1 and 2, the PKP can be decided. The size 5 is sufficient for undecidability. For which of the sizes 3 and 4 the PKP can be decided or not is still unclear (as of 2015). ${\displaystyle P}$

In addition, if the first component in all pairs is longer or shorter than the second ( or ), the instance is unsolvable. The same applies if a symbol occurs only in the first or only in the second components or if there is no pair that “begins the same” or “ends the same way” ( prefixes , suffixes ). ${\displaystyle p_{i}=\left(x_{i},y_{i}\right)}$ ${\displaystyle \forall i\colon \left|x_{i}\right|>\left|y_{i}\right|}$ ${\displaystyle \forall i\colon \left|x_{i}\right|<\left|y_{i}\right|}$

Trivia

According to an idea by Steffen Lange in 2011, Post's correspondence problem can serve as a starting point for a domino-like game family, the so-called PCP games.

See also

• Wang tiling

Individual evidence

1. ^ Andrzej Ehrenfeucht , G. Rozenberg: On the (Generalized) Post Correspondence Problem with Lists of Length 2 . In: Proc. 8th Int. Coll. Automata, Languages, and Programming . LNCS 115. Springer, 1981, pp. 219-234 .
2. ^ T. Neary: Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words . In: STACS 2015. Schloss Dagstuhl – Leibniz Center for Computer Science, 2015, pp. 649–661. doi : 10.4230 / LIPIcs.STACS.2015.649
3. ↑ Klaus Peter Jantke : PCP Games , 2016, Technical Report, series of reports by the Children's Media Department of the Fraunhofer Institute for Digital Media Technology IDMT, available online from Researchgate as a PDF file
4. ^ Turlough Neary: Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words . In: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) (=  Leibniz International Proceedings in Informatics (LIPIcs) ). tape 30 . Schloss Dagstuhl – Leibniz Center for Computer Science, Dagstuhl, Germany 2015, ISBN 978-3-939897-78-1 , p. 649–661 , doi : 10.4230 / LIPIcs.STACS.2015.649 ( dagstuhl.de [accessed on February 18, 2019]).

Web links

• Online PCP solution tool