資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學解釋計算理論中的對應問題 (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) 是否存在對應解。
解答
| X1 | X2 | X3 | |
| 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。
對應問題可以用兩種方式表示
多米諾骨牌形式。
表格形式
更新於：2021年6月14日
3K+ 次瀏覽
廣告