Problem z korespondencją pocztową

Problem korespondencji pocztowej (PCP), wprowadzony przez Emila Posta w 1946 r., Jest nierozstrzygalnym problemem decyzyjnym. Problem PCP nad alfabetem ∑ jest przedstawiony w następujący sposób -

Biorąc pod uwagę następujące dwie listy, M i N niepustych ciągów ponad ∑ -

M = (x 1 , x 2 , x 3 , ………, x n )

N = (y 1 , y 2 , y 3 , ………, y n )

Można powiedzieć, że istnieje rozwiązanie dotyczące korespondencji pocztowej, jeśli dla niektórych i 1 , i 2 , ………… i k , gdzie 1 ≤ i j ≤ n, warunek x i1 …… .x ik = y i1 ……. y ik spełnia.

Przykład 1

Sprawdź, czy listy

M = (abb, aa, aaa) i N = (bba, aaa, aa)

masz rozwiązanie dotyczące korespondencji pocztowej?

Rozwiązanie

x 1 x 2 x 3
M Wątek aa aaa
N Bba aaa aa

Tutaj,

x2x1x3 = ‘aaabbaaa’

i y2y1y3 = ‘aaabbaaa’

Widzimy to

x2x1x3 = y2y1y3

Stąd rozwiązaniem jest i = 2, j = 1, and k = 3.

Przykład 2

Sprawdź, czy listy M = (ab, bab, bbaaa) i N = (a, ba, bab) masz rozwiązanie dotyczące korespondencji pocztowej?

Rozwiązanie

x 1 x 2 x 3
M ab bab bbaaa
N za ba bab

W tym przypadku nie ma rozwiązania, ponieważ -

| x2x1x3 | ≠ | y2y1y3 | (Długości nie są takie same)

Stąd można powiedzieć, że jest to Problem dotyczący korespondencji pocztowej undecidable.