解释 TOC 中的邮政信函问题

该波斯特对应问题(PCP)由Emil邮政于1946年推出，是一个不可判定的判定问题。

字母 Σ 上的 PCP 问题是状态。给定以下两个列表，Σ- 上的非空字符串的 M 和 N

M = (x1, x2, x3,………, xn)
N = (y1, y2, y3,………, yn)

我们可以说有一个邮政通信解决方案，如果对于一些 i1,i2,………… ik,

其中 1≤ ij ≤ n，满足条件 xi1 …….xik = yi1 …….yik。

示例 1

找出列表 M = (abb, aa, aaa) 和 N = (bba, aaa, aa) 是否有 Post Correspondence Solution。

这里，

x2x1x3 = 'aaabbaaa'

和 y2y1y3 = 'aaabbaaa'

我们可以看到

x2x1x3 = y2y1y3

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

让我们看，在 PCP 问题中，我们有 N 个多米诺骨牌（瓷砖）。目的是按照分子组成的字符串与分母组成的字符串相同的顺序排列瓷砖。

简单来说，让我们假设我们有两个包含 N 个单词的列表，目的是找出这些单词以某种顺序连接起来，使两个列表产生相同的结果。

让我们尝试通过两个列表 A 和 B 来理解这一点

A=[aa, bb, abb] 和 B=[aab, ba, b]

现在对于序列 1、2、1、3，第一个列表将产生 aabbaaabb，第二个列表将产生相同的字符串 aabbaaabb。

所以这个 PCP 的解就变成了 1, 2, 1, 3。