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, MN của chuỗi không rỗng trên ∑ -

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

N = (y 1 , y 2 , y 3 , ………, 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 1 , i 2 , ………… 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,

x2x1x3 = ‘aaabbaaa’

y2y1y3 = ‘aaabbaaa’

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

x2x1x3 = y2y1y3

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)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ì -

| x2x1x3 | ≠ | y2y1y3 | (Độ dài không giống nhau)

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