郵便物の通信問題

ポスト対応問題は、 1946年にエミール・ポストによって導入された決定不能な決定問題である。^{[ 1 ]}停止問題や決定問題よりも単純なので、決定不能性の証明によく用いられる。

させて${\displaystyle A}$は少なくとも2つの記号を含むアルファベットとする。問題の入力は2つの有限リストで構成される。$\alpha_1, \ldots, \alpha_N$そして$\displaystyle \beta _{1},\ldots ,\beta _{N}}$言葉を超える${\displaystyle A}$この問題の解決策は、インデックスのシーケンスです。${\displaystyle (i_{k})_{1\leq k\leq K}}$と${\displaystyle K\geq 1}$そして${\displaystyle 1\leq i_{k}\leq N}$すべての人々のために${\displaystyle k}$、したがって

$\displaystyle \alpha _{i_{1}}\ldots \alpha _{i_{K}}=\beta _{i_{1}}\ldots \beta _{i_{K}}.}$

そこで問題となるのは、そのような解決策が存在するかどうかを判断することである。

PCP の決定不能性の最も一般的な証明は、特定の入力に対して任意のチューリング マシンの計算をシミュレートできる PCP のインスタンスを記述しています。一致は、入力がチューリング マシンによって受理される場合に限り発生します。チューリング マシンが入力を受理するかどうかを決定することは基本的な決定不能問題であるため、PCP も決定可能ではありません。以下の議論は、 Michael Sipserの教科書Introduction to the Theory of Computationに基づいています。^{[ 2 ]}

より詳しく説明すると、上部と下部の文字列はチューリングマシンの計算履歴を表します。つまり、初期状態を表す文字列、次の状態を表す文字列、といった具合に、受理状態を表す文字列で終わるまで続きます。状態文字列は区切り記号（通常は「#」）で区切られます。チューリングマシンの定義によれば、マシンの完全な状態は次の3つの部分から構成されます。

• テープの現在の内容。
• テープヘッドを操作する有限状態機械の現在の状態。
• テープヘッドのテープ上の現在位置。

テープには無限個のセルがありますが、そのうちの有限個の接頭辞のみが空白ではありません。これらを状態の一部として記録します。有限制御の状態を記述するために、有限状態機械のk個の状態それぞれに対して、 q ₁からq _kまでのラベルが付いた新しいシンボルを作成します。テープヘッドの位置に、テープの内容を記述する文字列に適切なシンボルを挿入することで、テープヘッドの位置と有限制御の現在の状態の両方を示します。アルファベット {0,1} の場合、典型的な状態は次のようになります。

101101110 q ₇ 00110。

単純な計算履歴は次のようになります。

q ₀ 101#1 q ₄ 01#11 q ₂ 1#1 q ₈ 10。

まず、このブロックから始めます。ここで、xは入力文字列、q0_は開始状態です。

最上位の状態は最下位の状態より1つ遅れて開始し、この遅れは最終段階まで続きます。次に、テープアルファベットの各記号aと # に対して、「コピー」ブロックがあり、これを変更せずにある状態から次の状態にコピーします。

また、機械が行う各位置遷移に対応するブロックも用意されており、テープヘッドの移動、有限状態の変化、周囲のシンボルの変化を示しています。例えば、ここではテープヘッドが状態4の0の上にあり、1を書き込んで右に移動し、状態7に変化します。

最後に、上側が受理状態に達すると、下側が最終的に追いついてマッチングを完了する機会が必要になります。これを可能にするために、受理状態に達した後は、後続の各マシンステップでテープヘッド付近のシンボルが1つずつ消えていき、シンボルがなくなるまで続きます。q _{f が}受理状態である場合、次の遷移ブロックでこれを表現できます。ここで、aはテープアルファベットのシンボルです。

証明を機能させるには、最後に1つの修正が必要です。上記のように、記号aを持つブロックは、解を満たすために単独で使用できます。修正方法の1つは、各テープ記号の2つの異なるバージョンを使用し、それらが1つの状態から次の状態へと交互に変化することを要求することです。この変更により、最初のタイルのみがマッチで最初に配置できます。また、計算の最終終了状態を強制することもできます。たとえば、別の記号 (ここでは # _endと表記) を使用して履歴全体を終了させます。

これは、静的なタイルパズルがチューリングマシンの計算をシミュレートできる方法を示している。

前の例

q ₀ 101#1 q ₄ 01#11 q ₂ 1#1 q ₈ 10。

これは、ポスト対応問題に対する以下の解として表されます。

PCPには多くの変種が検討されてきた。その理由の一つは、PCPから還元することで新しい問題の決定不能性を証明しようとする場合、最初に見つかる還元がPCP自体からではなく、一見弱いバージョンのPCPからであることが多いからである。

• この問題は、自由モノイドB ^∗から自由モノイドA ^∗へのモノイド射f、gを用いて表現できる。ここでBはサイズnである。問題は、 f ( w ) = g ( w )となるような単語wがB ⁺に存在するかどうかを判定することである。^{[ 3 ]}
• アルファベットの状態${\displaystyle A}$少なくとも 2 つのシンボルが必要です。なぜなら、問題は決定可能だからです。${\displaystyle A}$シンボルは1つだけです。
• 簡単な変形として、タイルの数nを固定する方法があります。この問題はn ≤ 2 の場合は決定可能ですが^{[ 4 ]} 、 n ≥ 5 の場合は決定不可能です。3 ≤ n ≤ 4の場合にこの問題が決定可能かどうかは不明です^{[ 5 ]。}
• 循環ポスト対応問題は、インデックスが${\displaystyle i_{1},i_{2},\ldots }$が見つかるので、$\displaystyle \alpha _{i_{1}}\cdots \alpha _{i_{k}}}$そして$\displaystyle \beta _{i_{1}}\cdots \beta _{i_{k}}}$これらは共役語であり、回転を法として等しい。この変種は決定不能である。^{[ 6 ]}
• PCP の最も重要な変種の 1 つは、重複タイルを含めてk個以下のタイルを使用して一致を見つけることができるかどうかを問う、有界ポスト対応問題です。総当たり探索では、この問題は O(2 ^k ) の時間で解決できますが、この問題はNP 完全であるため、これを改善するのは難しいかもしれません。^{[ 7 ]}ブール充足可能性問題のような NP 完全問題とは異なり、有界問題の小さな変種は RNP に対しても完全であることが示されており、これは入力がランダムに選択された場合でも困難であることを意味します (入力が均一に分布している場合、平均的には困難です)。^{[ 8 ]}
• PCP の別の変種はマーク付きポスト対応問題と呼ばれ、各$\displaystyle \alpha _{i}}$異なる記号で始めなければならず、$\displaystyle \beta _{i}}$また、異なる記号で始まる必要もある。Halava、Hirvensalo、およびde Wolfは、このバリエーションが指数時間で決定可能であることを示した。さらに、この要件を少し緩めて、最初の2文字のうち1文字だけが異なる必要がある場合（いわゆる2マーク付きポスト対応問題）、問題は再び決定不能になることを示した。^{[ 9 ]}
• 対称ポスト対応問題では、各ペアに対して追加の制約が課せられます。${\displaystyle (\alpha _{i},\beta _{i})}$ペア${\displaystyle (\beta _{i},\alpha _{i})=(\alpha _{j},\beta _{j})}$も存在します。この変種は決定不能です。^{[ 10 ]}
• ポスト埋め込み問題は、インデックスを探す別のバリエーションです。${\displaystyle i_{1},i_{2},\ldots }$そのため$\displaystyle \alpha _{i_{1}}\cdots \alpha _{i_{k}}}$は、(散在する)サブワードです。$\displaystyle \beta _{i_{1}}\cdots \beta _{i_{k}}}$この変種は、解が存在する場合、特に長さ1の解が存在するため、容易に判定可能です。より興味深いのは、正規ポスト埋め込み問題です。これは、与えられた正規言語（例えば、集合上の正規表現の形式で提出される）に属する解を探す別の変種です。${\displaystyle \{1,\ldots ,N\}}$) 正規ポスト埋め込み問題は依然として決定可能ですが、正規制約が追加されたため、すべての多重再帰関数よりも非常に高い複雑性を持っています。^{[ 11 ]}
• 同一性対応問題(ICP)は、(群アルファベット上の) の有限個の単語ペアの集合が、連結のシーケンスによって同一性ペアを生成できるかどうかを問う問題です。この問題は決定不能であり、次の群問題と同等です。すなわち、(群アルファベット上の) の有限個の単語ペアの集合によって生成される半群は群であるか。^{[ 12 ]}
• この問題は群の文脈で研究されており、モノイド準同型言語と同様の表現が用いられている。ポストの群に対する対応問題は、群準同型のペアを入力として受け取る。${\displaystyle f,g:F(B)\to G}$無料グループから${\displaystyle F(B)}$グループへ${\displaystyle G}$単語があるかどうかを判断しようとします${\displaystyle w}$で${\displaystyle F(B)}$そのため${\displaystyle f(w)=g(w)\neq 1}$決定可能であることが知られているのは、${\displaystyle G}$は実質的に冪零群であり、決定不能である。${\displaystyle G}$双曲群。^{[ 13 ]}マーク付きポスト対応問題の類似問題も、群に対して決定可能であることが知られている。^{[ 14 ]}

• エイタン・M・グラリ著『計算理論入門』第4章「ポストの対応問題」 。チョムスキー型0文法に基づくPCPの決定不能性の証明。
• Dong, Jing. 「PCPインスタンスの分析と解決」 2012年全国情報技術・コンピュータ科学会議。この論文では、特定のPCPインスタンスを解決するためのヒューリスティックルールについて述べている。
• オンラインPHPベースPCPソルバー
• PCPを自宅で
• PCP - 素敵な問題
• Javaで書かれたPCPソルバー
• 郵便通信の問題