Bài báo vấn đề

Bài toán Bưu điện (PCP), do Emil Post đưa ra vào năm 1946, là một bài toán khó quyết định. Vấn đề của PCP về bảng chữ cái ∑ được nêu như sau:

Đưa ra hai danh sách sau, M và N của chuỗi không rỗng trên ∑ -

M = (x ₁ , x ₂ , x ₃ , ………, x _n )

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

Chúng ta có thể nói rằng có một Lời giải tương ứng sau, nếu với một số i ₁ , i ₂ , ………… i _k , trong đó 1 ≤ i _j ≤ n, điều kiện x _i1 …… .x _ik = y _i1 ……. y _ik thỏa mãn.

ví dụ 1

Tìm xem các danh sách

M = (abb, aa, aaa) và N = (bba, aaa, aa)

có một Giải pháp Đăng bài?

Giải pháp

	x 1	x 2	x 3
M	Abb	aa	aaa
N	Bba	aaa	aa

Đây,

x₂x₁x₃ = ‘aaabbaaa’

và y₂y₁y₃ = ‘aaabbaaa’

Chúng tôi có thể thấy điều đó

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

Do đó, giải pháp là i = 2, j = 1, and k = 3.

Ví dụ 2

Tìm xem các danh sách M = (ab, bab, bbaaa) và N = (a, ba, bab) có một Giải pháp Đăng bài?

Giải pháp

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

Trong trường hợp này, không có giải pháp nào vì -

| x₂x₁x₃ | ≠ | y₂y₁y₃ | (Độ dài không giống nhau)

Do đó, có thể nói rằng Bài báo này là undecidable.