Post 通信问题

Post 通信问题 (PCP) 由埃米尔·波斯特 (Emil Post) 于 1946 年提出，是一个不可判定的决策问题。字母表 ∑ 上的 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₂y₁y₃ = 'aaabbaaa'

我们可以看出

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

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

示例 2

判断列表 M = (ab, bab, bbaaa) 和 N = (a, ba, bab) 有帖子对应解决方案吗？

解决方案

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

| x₂x₁x₃ | ≠ | y₂y₁y₃ | （长度不相同）

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