Проблема почтовой корреспонденции (PCP), представленная Эмилем Постом в 1946 году, является неразрешимой проблемой решения. Задача PCP над алфавитом stated формулируется следующим образом:
Учитывая следующие два списка, M и N непустых строк над ∑ —
M = (x 1 , x 2 , x 3 , ………, x n )
N = (y 1 , y 2 , y 3 , ………, y n )
Можно сказать, что существует решение для почтовой корреспонденции, если для некоторого i 1 , i 2 , ………… i k , где 1 ≤ i j ≤ n, условие x i1 …… .x ik = y i1 ……. у ик удовлетворяет.
Пример 1
Найти ли списки
M = (abb, aa, aaa) и N = (bba, aaa, aa)
есть решение для почтовой корреспонденции?
Решение
| х 1 | х 2 | х 3 | |
|---|---|---|---|
| M | уток | аа | ааа |
| N | BBA | ааа | аа |
Вот,
х 2 х 1 х 3 = ‘аааббааа’
и y 2 y 1 y 3 = ‘aaabbaaa’
Мы это видим
х 2 х 1 х 3 = у 2 у 1 у 3
Следовательно, решение i = 2, j = 1 и k = 3.
Пример 2
Найдите, имеют ли списки M = (ab, bab, bbaaa) и N = (a, ba, bab) решение для почтовой корреспонденции?
Решение
| х 1 | х 2 | х 3 | |
|---|---|---|---|
| M | аб | бабы | bbaaa |
| N | ба | бабы |
В этом случае нет решения, потому что —
| х 2 х 1 х 3 | ≠ | y 2 y 1 y 3 | (Длина не одинакова)
Следовательно, можно сказать, что эта проблема почтовой корреспонденции неразрешима .