Undecidable decision problem introduced by Emil Post
ポスト 対応問題 は、 1946年に エミール・ポスト によって導入された決定 不能な 決定問題 です。 [1] 停止問題 や 決定問題 よりも単純なので、 決定不能性の証明によく使用されます。
問題の定義 少なくとも2つの記号を含むアルファベットを とする。問題の入力は 2つの有限リストと 上の単語からなる 。 この 問題 の解は、 すべての について と の 添え字の 列 で、 A {\displaystyle A} α 1 , … , α N {\displaystyle \alpha _{1},\ldots ,\alpha _{N}} β 1 , … , β N {\displaystyle \beta _{1},\ldots ,\beta _{N}} A {\displaystyle A} ( i k ) 1 ≤ k ≤ K {\displaystyle (i_{k})_{1\leq k\leq K}} K ≥ 1 {\displaystyle K\geq 1} 1 ≤ i k ≤ N {\displaystyle 1\leq i_{k}\leq N} k {\displaystyle k}
α i 1 … α i K = β i 1 … β i K . {\displaystyle \alpha _{i_{1}}\ldots \alpha _{i_{K}}=\beta _{i_{1}}\ldots \beta _{i_{K}}.} その場合の決定問題は、そのような解決策が存在するかどうかを判断することです。
代替定義 g : ( i 1 , … , i K ) ↦ α i 1 … α i K {\displaystyle g:(i_{1},\ldots ,i_{K})\mapsto \alpha _{i_{1}}\ldots \alpha _{i_{K}}} h : ( i 1 , … , i K ) ↦ β i 1 … β i K . {\displaystyle h:(i_{1},\ldots ,i_{K})\mapsto \beta _{i_{1}}\ldots \beta _{i_{K}}.} これは文献でよく見られる同等の代替定義を生じ、それによれば、共通のドメインと共通のコドメインを持つ任意の2つの準同型写像はポスト対応問題の例を形成し、 ドメイン内に 空でない単語が存在するかどうかを問うことになる。 g , h {\displaystyle g,h} w {\displaystyle w}
g ( w ) = h ( w ) {\displaystyle g(w)=h(w)} 。 この問題をパズルの一種として簡単に説明する別の定義があります。まず、各辺に2本のひもを持つドミノの集合を考えます。個々のドミノは次のようになります。
[ a a b ] {\displaystyle {\begin{bmatrix}a\\ab\end{bmatrix}}} ドミノの集まりは次のようになります
[ b c c a ] , [ a a b ] , [ c a a ] , [ a b c c ] {\displaystyle {{\begin{bmatrix}bc\\ca\end{bmatrix}},{\begin{bmatrix}a\\ab\end{bmatrix}},{\begin{bmatrix}ca\\a\end{bmatrix}},{\begin{bmatrix}abc\\c\end{bmatrix}}}} 。 課題は、これらのドミノ（重複可）のリストを作成し、上部の記号を読み取って得られる文字列が下部の記号の文字列と一致するようにすることです。このリストはマッチと呼ばれます。ポスト対応問題は、ドミノの集合にマッチがあるかどうかを判定することです。例えば、次のリストはこのパズルのマッチです。
[ a a b ] , [ b c c a ] , [ a a b ] , [ a b c c ] {\displaystyle {{\begin{bmatrix}a\\ab\end{bmatrix}},{\begin{bmatrix}bc\\ca\end{bmatrix}},{\begin{bmatrix}a\\ab\end{bmatrix}},{\begin{bmatrix}abc\\c\end{bmatrix}}}} 。 ドミノのコレクションによっては、一致するものを見つけられない場合があります。例えば、
[ a b c a b ] , [ c a a ] , [ a c c b a ] {\displaystyle {{\begin{bmatrix}abc\\ab\end{bmatrix}},{\begin{bmatrix}ca\\a\end{bmatrix}},{\begin{bmatrix}acc\\ba\end{bmatrix}}}} 。 すべての上位文字列が対応する下位文字列よりも長いため、一致を含めることはできません。
問題の例
例1 次の 2 つのリストを考えてみましょう。
この問題の解は（3, 2, 3, 1）というシーケンスになります。
α 3 α 2 α 3 α 1 = b b a ⋅ a b ⋅ b b a ⋅ a = b b a a b b b a a = b b ⋅ a a ⋅ b b ⋅ b a a = β 3 β 2 β 3 β 1 . {\displaystyle \alpha _{3}\alpha _{2}\alpha _{3}\alpha _{1}=bba\cdot ab\cdot bba\cdot a=bbaabbbaa=bb\cdot aa\cdot bb\cdot baa=\beta _{3}\beta _{2}\beta _{3}\beta _{1}.} さらに、(3, 2, 3, 1) は解なので、(3, 2, 3, 1, 3, 2, 3, 1) などのその「繰り返し」もすべて解です。つまり、解が存在する場合、この繰り返しの種類の解は無限に存在することになります。
しかし、もし 2 つのリストがそれらのセットからの と のみで構成されていたら 、 解決策は存在しません (そのような α 文字列の最後の文字はその前の文字と同じではありませんが、β は同じ文字のペアのみを構築します)。 α 2 , α 3 {\displaystyle \alpha _{2},\alpha _{3}} β 2 , β 3 {\displaystyle \beta _{2},\beta _{3}}
郵便対応問題の例を見る便利な方法は、次のような形式のブロックの集合として見ることである。
それぞれの種類のブロックは無制限に供給可能であるため、上記の例は次のように考えられます。
ここで、ソルバーはこれら3種類のブロックをそれぞれ無限に供給します。解は、上段のセルの文字列が下段のセルの文字列と一致するようにブロックを隣り合わせに配置する方法に対応します。つまり、上記の例の解は次のようになります。
私 1 = 3
i 2 = 2
i 3 = 3
i 4 = 1
例2 再びブロックを使用して問題のインスタンスを表すと、次の例は、単に解決策を「繰り返す」ことによって得られる種類の解決策に加えて、無限に多くの解決策を持つ例です。
この例では、(1, 2, 2, . . ., 2, 3) という形式のすべてのシーケンスがソリューションになります (それらの繰り返しに加えて)。
決定不能性の証明スケッチ PCPの決定不能性の最も一般的な証明は、 特定の入力に対する任意の チューリングマシンの計算をシミュレートできるPCPのインスタンスを記述するものである。入力がチューリングマシンに受け入れられる場合にのみ、一致が発生する。 チューリングマシンが入力を受け入れるかどうかを決定することは基本的な決定不能問題であるため、PCPも決定不能ではない。以下の議論は、 マイケル・シプサー の教科書 『計算理論入門』 [2] に基づいている 。
より詳細に説明すると、上部と下部の文字列はチューリングマシンの 計算履歴 となります。つまり、初期状態を表す文字列、次の状態を表す文字列、そして最後に受理状態を表す文字列が続くことになります。状態文字列は、何らかの区切り記号（通常は#で表記されます）で区切られます。チューリングマシンの定義によれば、マシンの完全な状態は次の3つの部分で構成されます。
テープ内の現在の内容。 テープ ヘッドを操作する 有限状態マシン の現在の状態。 テープ上のテープ ヘッドの現在の位置。 テープには無限のセルがありますが、そのうち空白でないのは有限個のプレフィックスだけです。これらを状態の一部として記録します。有限制御の状態を記述するために、 有限状態マシンの k個の状態それぞれについて、 q 1 から q k までというラベルの付いた新しいシンボルを作成します。テープヘッドの位置におけるテープの内容を記述する文字列に適切なシンボルを挿入することで、テープヘッドの位置と有限制御の現在の状態の両方を示します。アルファベット {0,1} の場合、典型的な状態は次のようになります。
101101110 q 7 00110。
単純な計算履歴は次のようになります。
q 0 101#1 q 4 01#11 q 2 1#1 q 8 10。
このブロックから始めます。ここで、 x は入力文字列、 q 0 は開始状態です。
上段は下段より1状態遅れて開始し、この遅れは最終段まで維持されます。次に、テープアルファベットの各記号 a と#について、「コピー」ブロックが存在します。このブロックは、記号をある状態から次の状態へと変更せずにコピーします。
また、マシンが実行可能な各位置遷移に対応するブロックも用意しており、テープヘッドの動き、有限状態の変化、そして周囲のシンボルに何が起こるかを示しています。例えば、ここではテープヘッドは状態4で0の上にあり、その後1を書き込んで右に移動し、状態7に変化します。
最後に、トップが受理状態に達したとき、ボトムは最終的に追いついて一致を完了させる機会が必要です。これを可能にするために、計算を拡張し、受理状態に達した後は、以降の各マシンステップでテープヘッド近くのシンボルが1つずつ消え、最終的にシンボルがなくなるまで消えるようにします。q f が受理状態である場合、これを次の遷移ブロックで表すことができます。ここで、 a は テープのアルファベットシンボルです。
証明を成立させるには、最後にもう一つ変更が必要です。上記のように、記号 a のブロックは単独で使用することで解を満たすことができます。これを適応させる一つの方法は、各テープ記号の異なるバージョンを2つ用意し、それらが交互に状態を変えるようにすることです。この変更により、マッチにおいて最初に移動できるタイルは最初のタイルのみになります。また、計算の最終終了状態を強制することもできます。例えば、別の記号（ここでは # end と表記）を使用して、履歴全体を終了させるなどです。
これは、静的なタイル パズルでチューリング マシンの計算をシミュレートする方法を示しています。
前の例
q 0 101#1 q 4 01#11 q 2 1#1 q 8 10。
は、郵便対応問題に対する次の解として表されます。
変種 PCPには多くの変種が検討されてきました。その理由の一つは、PCPからの帰着によって新しい問題の決定不能性を証明しようとすると、最初に見つかる帰着がPCP自体からではなく、明らかにより弱いバージョンからであることがよくあるからです。
この問題は、自由モノイド B ∗ から自由モノイド A ∗への モノイド射 f , g を用いて表現することができる。 ここで Bは n の大きさである。問題は、 B + に単語 w が存在し、 f ( w ) = g ( w )となるかどうかを判定することである 。 [3] アルファベット に少なくとも 2 つの記号があるという条件が必要です。 記号が 1 つしかない場合でも問題は決定可能です。 A {\displaystyle A} A {\displaystyle A} 単純な変形として 、タイルの数を nに固定する方法がある。この問題は n ≤ 2の場合には決定可能である が [4] 、 n ≥ 5の場合には決定不可能である。3 ≤ n ≤ 4の 場合には決定可能かどうかは不明である [5]。 循環 ポスト対応問題は、 と が 共役語 となるようなインデックス 、すなわち回転を法として等しい インデックス が見つかるかどうかを問うものである。この変種は決定不可能である。 [6] i 1 , i 2 , … {\displaystyle i_{1},i_{2},\ldots } α i 1 ⋯ α i k {\displaystyle \alpha _{i_{1}}\cdots \alpha _{i_{k}}} β i 1 ⋯ β i k {\displaystyle \beta _{i_{1}}\cdots \beta _{i_{k}}} PCPの最も重要な変種の一つは、 境界付き ポスト対応問題 である。これは、繰り返しタイルを含め、 k 個以下のタイルを使って一致するものを見つけられるかどうかを問う問題である。総当たり探索ではO(2 k )の時間でこの問題を解くことができるが、この問題はNP完全で あるため、改善が難しい可能性がある 。 [7] ブール充足可能性問題 のような一部のNP完全問題とは異なり 、境界付き問題の小さなバリエーションはRNPに対しても完全であることが示された。つまり、入力がランダムに選択された場合でも難しいままである（均一に分布した入力に対して平均的に難しい）。 [8] PCPの別の変種はマーク付き 後対応問題 と呼ばれ 、各文字が 異なる記号で始まり、またそれぞれが 異なる記号で始まらなければならない。ハラヴァ、ヒルヴェンサロ、そしてデ・ウルフは、この変種が 指数時間 で決定可能であることを示した。さらに、彼らはこの要件をわずかに緩和し、最初の2文字のうち1文字のみが異なればよいようにした場合（いわゆる2マーク付き後対応問題）、問題は再び決定不可能になることを示した。 [9] α i {\displaystyle \alpha _{i}} β i {\displaystyle \beta _{i}} ポスト 埋め込み問題は 、が の （散在した）部分語 と なるような インデックスを探すという別の変種です 。この変種は、いくつかの解が存在する場合、特に長さ1の解が存在する場合、簡単に決定可能です。より興味深いのは、 正規 ポスト埋め込み問題です。これは、与えられた 正規言語 （例えば、集合 上の正規表現の形で提示される） に属する解を探すという、さらなる変種 です。正規ポスト埋め込み問題は依然として決定可能ですが、追加された正規制約のために、あらゆる多重再帰関数を支配する非常に高い計算量を持ちます。 [10] i 1 , i 2 , … {\displaystyle i_{1},i_{2},\ldots } α i 1 ⋯ α i k {\displaystyle \alpha _{i_{1}}\cdots \alpha _{i_{k}}} β i 1 ⋯ β i k {\displaystyle \beta _{i_{1}}\cdots \beta _{i_{k}}} { 1 , … , N } {\displaystyle \{1,\ldots ,N\}} 恒等 対応問題 （ICP）は、単語対の有限集合（グループアルファベット上）から、連結列によって恒等対を生成できるかどうかを問う問題である。この問題は決定不能であり、次の群問題と同値である。「単語対の有限集合（グループアルファベット上）から生成される半群は群か？」 [11]
参考文献 ^ EL Post (1946). 「再帰的に解けない問題の変種」 (PDF) . Bull. Amer. Math. Soc. 52 (4): 264– 269. doi :10.1090/s0002-9904-1946-08555-9. S2CID 122948861. ^ マイケル・シプサー (2005). 「単純な決定不能問題」. 計算理論入門 （第2版）. トムソン・コース・テクノロジー. pp. 199– 205. ISBN 0-534-95097-3 。 ^ Salomaa, Arto (1981). Jewels of Formal Language Theory . Pitman Publishing. pp. 74– 75. ISBN 0-273-08522-0 . Zbl 0487.68064. ^ Ehrenfeucht, A. ; Karhumäki, J. ; Rozenberg, G. (1982年11月). 「2つの単語からなるリストにおける（一般化された）事後対応問題は決定可能である」. 理論計算機科学 . 21 (2): 119– 144. doi :10.1016/0304-3975(89)90080-7. ^ T. Neary (2015). 「バイナリタグシステムにおける決定不能性と5対の単語の対応付け問題」 Ernst W. MayrとNicolas Ollinger (編). 第32回国際コンピュータサイエンス理論シンポジウム (STACS 2015) . STACS 2015. 第30巻. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 649– 661. doi : 10.4230/LIPIcs.STACS.2015.649 . ^ K. Ruohonen (1983). 「ポストの対応問題のいくつかの変種について」. Acta Informatica . 19 (4). Springer: 357– 367. doi :10.1007/BF00290732. S2CID 20637902. ^ Michael R. Garey 、 David S. Johnson (1979). 『コンピュータとイントラクタビリティ：NP完全性理論へのガイド』 WH Freeman. p. 228. ISBN 0-7167-1045-5 。 ^ Y. Gurevich (1991). 「平均ケース完全性」 (PDF) . J. Comput. Syst. Sci. 42 (3). Elsevier Science: 346– 398. doi :10.1016/0022-0000(91)90007-R. hdl :2027.42/29307. ^ V. Halava; M. Hirvensalo; R. de Wolf (2001). 「マーク付きPCPは決定可能」. Theor. Comput. Sci . 255 ( 1– 2). Elsevier Science: 193– 204. doi :10.1016/S0304-3975(99)00163-2. ^ P. Chambart; Ph. Schnoebelen (2007). ポスト埋め込み問題は原始再帰的ではない、チャネルシステムへの応用 (PDF) . Lecture Notes in Computer Science. Vol. 4855. Springer. pp. 265– 276. doi :10.1007/978-3-540-77050-3_22. ISBN 978-3-540-77049-7 。 ^ Paul C. Bell; Igor Potapov (2010). 「恒等対応問題の決定不能性と語群および行列半群への応用について」. International Journal of Foundations of Computer Science . 21 (6). World Scientific: 963– 978. arXiv : 0902.1975 . doi :10.1142/S0129054110007660.
外部リンク エイタン・M・グラリ著 『計算理論入門』第4章「ポストの対応問題」。 チョムスキー0型文法 に基づくPCPの決定不能性の証明 。 Dong, Jing. 「PCPインスタンスの分析と解法」2012年 National Conference on Information Technology and Computer Science. この論文では、特定のPCPインスタンスを解くためのヒューリスティックな規則について説明しています。 オンライン PHP ベースの PCP ソルバー 自宅でのPCP PCP - 良い問題 JavaのPCPソルバー 郵便対応の問題 
