解释计算理论中的对应问题 (Post Correspondence Problem)

对应问题 (Post Correspondence Problem, 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。

例 1

判断列表 M = (abb, aa, aaa) 和 N = (bba, aaa, aa) 是否存在对应解。

这里，

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。

Bhanu Priya

更新于：2021年6月14日

3K+ 次浏览

完成课程获得认证