Postsches Korrespondenzproblem

Postsches Korrespondenzproblem

Das Postsche Korrespondenzproblem (nach Emil Leon Post, abgekürzt auch PKP oder englisch PCP) 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. Man nennt P auch einen Problemfall oder eine Instanz.

Eine nicht-leere Folge I = i_1, i_2, \ldots, i_n von Indices aus \{1, 2, \ldots, m\} heißt eine Lösung zum Problemfall P, falls die Konkatenation (Verkettung) der Wörter \left. {x_{i_1},x_{i_2},\ldots,x_{i_n}}\right. gleich der Konkatenation der Wörter \left.{y_{i_1},y_{i_2},\ldots,y_{i_n}}\right. ist.

Das Korrespondenzproblem ist dann die Aufgabe, zu einem beliebigen Problemfall anzugeben, ob er eine Lösung besitzt oder nicht. Das Korrespondenzproblem ist unentscheidbar, das heißt, es gibt keinen Algorithmus, der zu einem beliebigen Problemfall die richtige Antwort gibt.

Inhaltsverzeichnis

Anschauliche Darstellung

Die Wortpaare (xi,yi) eines Problemfalls kann man sich gut als "Dominosteine" vorstellen, bei denen auf der einen Hälfte xi und auf der anderen Hälfte yi steht. Es gibt m Arten von Dominosteinen und von jeder Art stehen unendlich viele Dominosteine zur Verfügung.

Das Korrespondenzproblem lässt sich nun also wie folgt verstehen: Gibt es eine Folge von Dominosteinen, so dass die Wörter auf der oberen Hälfte der Dominosteine von links nach rechts gelesen dasselbe Wort ergeben, wie die von links nach rechts gelesenen Wörter aus der unteren Hälfte der zusammengelegten Dominosteine?

Beispiel

Gegeben:

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

\left. x_1=1 \right., \left. x_2=10 \right., \left. x_3=011 \right.
\left. y_1=101 \right., \left. y_2=00 \right., \left. y_3=11 \right.

Lösung:

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

Es gilt: x_1\cdot x_3\cdot x_2\cdot x_3 = 1\cdot 011\cdot 10\cdot 011 = 101110011 = 101\cdot 11\cdot 00\cdot 11 = y_1 \cdot y_3 \cdot y_2\cdot y_3.

I1 ist also eine Lösung des Problemfalls P1.

Als Dominofolge: \frac{1}{101}\ \frac{011}{11}\ \frac{10}{00}\ \frac{011}{11}.

Bemerkungen dazu:

Natürlich bildet jede Verkettung zweier Lösungen oder einer Lösung mit sich selbst wieder eine Lösung. Man kann also fragen, ob eine Lösung aus kürzeren Lösungen zusammengesetzt ist. Die Lösung \left(1, 3, 2, 3\right) ist nicht aus kürzeren Lösungen zusammengesetzt: sie ist primitiv. Manchmal gibt es mehrere primitive Lösungen, nicht jedoch in diesem Beispiel.

Das Beispiel P1 erweckt vielleicht den Eindruck, dass das Postsche Korrespondenzproblem gar nicht so schwierig ist. Es gibt jedoch auch Problemfälle, die nur sehr lange Lösungen haben.

Hierzu ein Beispiel P2

\left. x_1 = 001 \right., \left. x_2 = 01 \right., \left. x_3 = 01 \right., \left. x_4 = 10 \right.
\left. y_1 = 0 \right., \left. y_2 = 011 \right., \left. y_3 = 101 \right., \left. y_4 = 001 \right.

Eine kürzeste Lösung besteht schon aus 66 Paaren:

I1 = (2,4,3,4,4,2,1,2,4,3,4,3,4,4,3,4,4,2,1,4,4,2,1,3,4,1,1,3,4,4,4,2,1,2,1,1,1,3,4,3,4,1,2,1,4,4,2,1,4,1,1,3,4,1,1,3,1,1,3,1,2,1,4,1,1,3)

An dieser Lösung kann man leicht die Komplexität des Problems erkennen.

Grenzen zwischen Entscheidbarkeit und Unentscheidbarkeit

Durch Probieren lässt sich eine Lösung nach endlicher Zeit finden, sofern es eine gibt, wenn es jedoch keine Lösung gibt wird der Algorithmus nicht terminieren. Das PKP ist somit ein unentscheidbares Problem, denn es ist nur semi-entscheidbar.

Sonderfälle
Durch Einschränkung des Alphabets wird das Problem "einfacher". Lässt man nur Wortpaare über einem einelementigen Alphabet zu, dann wird aus dem PKP ein entscheidbares Problem. Das PKP eingeschränkt auf ein zweielementiges Alphabet dagegen bleibt unentscheidbar, denn ein beliebiges Alphabet kann in einem zweielementigen Alphabet kodiert werden.

Man kann auch die Größe, das heißt die Anzahl der Paare, in den Problemfällen P einschränken. Für die Größen 1 und 2 wird das PKP entscheidbar.[1] Die Größe 7 reicht aus für Unentscheidbarkeit.[2] Für welche der Größen 3 bis 6 das PKP entscheidbar ist oder nicht, ist noch ungeklärt (Stand 2011).

Außerdem gilt: wenn in allen Paaren pi = (xi,yi) die erste Komponente länger bzw. kürzer als die zweite ist (∀pi | xi | > | yi | oder ∀pi | xi | < | yi | ) ist das PKP unlösbar. Genauso wenn ein Symbol nur in den ersten oder nur in den zweiten Komponenten vorkommt oder wenn es kein Paar gibt das "gleich losgeht" oder "gleich endet" (Präfixe, Suffixe).

Siehe auch

Einzelnachweise

  1. A. Ehrenfeucht, G. Rozenberg: On the (Generalized) Post Correspondence Problem with Lists of Length 2. In: Proc. 8th Int. Coll. Automata, Languages, and Programming. LNCS 115, Springer, 1981, S. 219-234.
  2. Yuri Matiyasevich, Geraud Senizergues: Decision Problems for Semi-Thue Systems with a few Rules. In: Proc. 11th Symp. Logic in Computer Science. Springer, 1996, S. 523-531.

Weblinks


Wikimedia Foundation.

См. также в других словарях:

  • Entscheidbare Menge — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat… …   Deutsch Wikipedia

  • Entscheidbarkeit — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat… …   Deutsch Wikipedia

  • Entscheidungsproblem — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat… …   Deutsch Wikipedia

  • Rekursiv entscheidbar — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat… …   Deutsch Wikipedia

  • Rekursiv entscheidbare Menge — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat… …   Deutsch Wikipedia

  • Semientscheidbarkeit — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat… …   Deutsch Wikipedia

  • Unentscheidbares Problem — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat… …   Deutsch Wikipedia

  • Unentscheidbarkeit — Eine Eigenschaft auf einer Menge heißt entscheidbar (auch: rekursiv), wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat… …   Deutsch Wikipedia

  • Emil Post — Emil Leon Post Emil Leon Post (* 11. Februar 1897 in Augustów, Polen; † 21. April 1954 in New York, USA) war ein polnisch US amerikanischer Mathematiker und Logiker …   Deutsch Wikipedia

  • PKP — ist Abkürzung für: Polskie Koleje Państwowe (Polnische Staatsbahn), die wichtigste polnische Eisenbahngesellschaft Postsches Korrespondenzproblem, ein Problem aus der Theoretischen Informatik Public Knowledge Project, ein Forschungsprojekt, das… …   Deutsch Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»