帖子通信问题

---

埃米尔·波斯特 (Emil Post) 于 1946 年提出的邮政对应问题 (PCP) 是一个不可判定的决策问题。字母表 Σ 上的 PCP 问题表述如下 -

给定以下两个列表，M和N超过 Σ 的非空字符串 -

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

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

我们可以说存在一个后对应解，如果对于某个 i ₁ ,i ₂ ,………… i _k，其中 1 ≤ i _j ≤ n，则条件 x _i1 …….x _ik = y _i1 ……。 y _ik满足。

实施例1

查找是否列表

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

有邮政通信解决方案吗？

解决方案

这里，

x ₂ x ₁ x ₃ = 'aaabbaaa'

y 2 y ₁ y _{3 = '} aaabbaaa'

我们可以看到

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

因此，解为i = 2、j = 1、k = 3。

实施例2

求列表M = (ab, bab, bbaaa)和N = (a, ba, bab)是否有 Post Correspondence Solution？

解决方案

在这种情况下，没有解决方案，因为 -

| x ₂ x ₁ x ₃ | ≠ | y ₂ y ₁ y ₃ | （长度不一样）

因此，可以说这个帖子对应问题是不可判定的。