解释 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)是否有PostCorrespondenceSolution。
解决方案
这里，
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。
后通信问题可以用两种方式表示
多米诺骨牌。
表格形式