Postsches Korrespondenzproblem

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Das Postsche Korrespondenzproblem (nach Emil Leon Post) ist ein Beispiel für ein unentscheidbares Problem in der Theoretischen Informatik. Es wird häufig verwendet, um mittels Reduktion die Unentscheidbarkeit anderer Probleme zu zeigen.

Gegeben ist eine endliche Folge $P$ von Paaren $\left((x_1,y_1),(x_2,y_2),\ldots,(x_m,y_m)\right)$ von nicht-leeren Wörtern $x_1, x_2, \ldots, x_m, y_1, y_2, \ldots, y_m$ über einem endlichen Alphabet.

Als Entscheidungsproblem stellt sich nun die folgende Frage: Existiert eine nicht-leere Folge $I = i_1, i_2, \ldots, i_n$ von Indizies aus $\{1, 2, \ldots, m\}$ , so dass die Verkettung (Konkatenation) der Wörter $\left. {x_{i_1},x_{i_2},\ldots,x_{i_n}}\right.$ gleich der Verkettung der Wörter $\left.{y_{i_1},y_{i_2},\ldots,y_{i_n}}\right.$ ist?

[Bearbeiten] Anschauliche Interpretation

Wie oben erklärt, besitzt jede der beiden gegebenen Listen $m$ -viele Worte über dem Eingabealphabet. Die paarweise Darstellung der Elemente, sprich $\left((x_1,y_1),(x_2,y_2),\ldots,(x_m,y_m)\right)$ , kann man sich dabei sehr gut als "Dominosteine" (oder auch andere, beschreibbare Spielsteine) darstellen: Es gibt $m$ -viele Dominosteine und von jedem Typ stehen unendlich viele Dominosteine des gleichen Typs zur Verfügung. Dabei steht auf einem Dominostein $d i$ auf der oberen Hälfte das Wort $x i$ und auf der unteren Hälfte das Wort $y_i \ \forall i \in \left\{ 1 , ... , m \right\}$ geschrieben.

Das PKP lässt sich nun also wie folgt verstehen: Welche Dominosteine müssen in welcher Reihenfolge hintereinander gelegt werden, so dass die Worte auf der oberen Hälfte der Dominosteine (von links nach rechts gelesen) dasselbe Wort ergeben, wie die (von links nach rechts gelesenen) Worte aus der unteren Hälfte der zusammengelegten Dominosteine?

[Bearbeiten] Beispiel

Gegeben:

$P_1 = \left( (1,101), (10,00), (011,11) \right)$

$\left. x_1=1 \right.,$ $\left. y_1=101 \right.$

$\left. x_2=10 \right.,$ $\left. y_2=00 \right.$

$\left. x_3=011 \right.,$ $\left. y_3=11 \right.$

Lösung:

$I_1 = \left( 1, 3, 2, 3 \right)$

$\left. {1|0\ 1\ 1|1\ 0|0\ 1\ 1} \right.$

$\left. {1\ 0\ 1|1\ 1|0\ 0|1\ 1} \right.$

Resultat:

Die beiden verketteten Wörter sind identisch, d.h. die PCP-Instanz $P 1$ ist beispielsweise mit der Indexfolge $\left(1, 3, 2, 3\right)$ lösbar. Manchmal gibt es mehrere primitive Lösungen, was in diesem Beispiel jedoch nicht der Fall ist. Natürlich bildet jede vollständige Verkettung einer solchen Indexfolge mit sich selbst oder einer anderen Lösung wieder eine Lösung.

Das Beispiel $P 1$ erweckt vielleicht den Eindruck, dass das Postsche Korrespondenzproblem gar nicht so schwierig ist. Jedoch muss ein adäquater Lösungsalgorithmus für alle Instanzen eine korrekte Antwort geben, d.h. er muss in endlicher Zeit entscheiden, ob eine solche Indexfolge $I$ für ein gegebenes $P$ existiert oder nicht.

[Bearbeiten] Grenzen der Unentscheidbarkeit

Das obige Entscheidungsproblem ist zwar im Allgemeinen unentscheidbar, lässt man jedoch nur Wortpaare über einem unären Alphabet (Alphabet mit nur einem Symbol) zu oder schränkt man die Anzahl der Paare in $P$ zu stark ein, dann wird das Problem doch wieder entscheidbar. Andererseits reicht ein binäres Alphabet (Alphabet mit zwei Symbolen) für die Unentscheidbarkeit aus, weil größere Alphabete damit einfach kodiert werden können.