對應郵局問題



對應郵局問題 (PCP) 由 Emil Post 於 1946 年提出,是一個不可判定的判定問題。在字母表 ∑ 上的 PCP 問題陳述如下:

給定以下兩個列表,**M** 和 **N**,它們包含在 ∑ 上的非空字串:

M = (x1, x2, x3,………, xn)

N = (y1, y2, y3,………, yn)

如果對於某些 i1,i2,………… ik,其中 1 ≤ ij ≤ n,條件 xi1 …….xik = yi1 …….yik 成立,則可以說存在 Post 對應解。

示例 1

查詢列表

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

是否存在 Post 對應解?

解答

x1 x2 x3
M abb aa aaa
N bba aaa aa

這裡:

x2x1x3 = ‘aaabbaaa’

並且 y2y1y3 = ‘aaabbaaa’

我們可以看到

x2x1x3 = y2y1y3

因此,解為 i = 2, j = 1, k = 3.

示例 2

查詢列表 M = (ab, bab, bbaaa)N = (a, ba, bab) 是否存在 Post 對應解?

解答

x1 x2 x3
M ab bab bbaaa
N a ba bab

在這種情況下,不存在解,因為:

| x2x1x3 | ≠ | y2y1y3 | (長度不相等)

因此,可以說這個 Post 對應問題是不可判定的

廣告