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 ₁ , x ₂ , x ₃ , ………, x _n )

N = (y ₁ , y ₂ , y ₃ , ………, y _n )

Można powiedzieć, że istnieje rozwiązanie dotyczące korespondencji pocztowej, jeśli dla niektórych i ₁ , i ₂ , ………… 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,

x₂x₁x₃ = ‘aaabbaaa’

i y₂y₁y₃ = ‘aaabbaaa’

Widzimy to

x₂x₁x₃ = y₂y₁y₃

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ż -

| x₂x₁x₃ | ≠ | y₂y₁y₃ | (Długości nie są takie same)

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