Das Ähnlichkeitsproblem von Post ist ein unentscheidbares Entscheidungsproblem, das von Emil Post 1946 eingeführt wurde. Weil es einfacher ist als das stockende Problem und Entscheidungsproblem, wird es häufig in Beweisen der Unentscheidbarkeit verwendet.

Definition des Problems

Der Eingang des Problems besteht aus zwei begrenzten Listen und von Wörtern über ein Alphabet, das mindestens zwei Symbole hat. Eine Lösung dieses Problems ist eine Folge von Indizes mit und für alle, solch dass

:

Das Entscheidungsproblem ist dann zu entscheiden, ob solch eine Lösung besteht oder nicht.

Beispiel-Beispiele des Problems

Beispiel 1

Denken Sie die folgenden zwei Listen:

</td>

</td></tr></Tisch>

Eine Lösung dieses Problems würde die Folge (3, 2, 3, 1), weil sein

:

Außerdem, seitdem (3, 2, 3, 1) ist eine Lösung, auch sind alle seine "Wiederholungen", solcher als (3, 2, 3, 1, 3, 2, 3, 1) usw.; d. h. wenn eine Lösung besteht, gibt es ungeheuer viele Lösungen dieser wiederholenden Art.

Jedoch, wenn die zwei Listen aus nur bestanden hätten und, dann hätte es keine Lösung gegeben (weil dann kein zusammenpassendes Paar denselben letzten Brief haben würde, wie am Ende einer Lösung vorkommen muss).

Eine günstige Weise, ein Beispiel eines Postähnlichkeitsproblems anzusehen, ist als eine Sammlung von Blöcken der Form

</td></tr></Tisch>

dort eine unbegrenzte Versorgung jedes Typs des Blocks seiend. So wird das obengenannte Beispiel als angesehen

</td></td></td></tr></tr></Tisch>

wo der solver eine endlose Versorgung von jedem dieser drei Block-Typen hat. Eine Lösung entspricht einer Weise, Blöcke neben einander zu legen, so dass die Schnur in den Spitzenzellen der Schnur in den untersten Zellen entspricht. Dann entspricht die Lösung des obengenannten Beispiels:

</td></td></td></td></tr></tr></Tisch>

Beispiel 2

Wieder mit Blöcken, um ein Beispiel des Problems zu vertreten, ist der folgende ein Beispiel, das ungeheuer viele Lösungen zusätzlich zur erhaltenen Art durch das bloße "Wiederholen" einer Lösung hat.

</td></td></td></tr></tr></Tisch>

In diesem Beispiel ist jede Folge der Form (1, 2, 2..., 2, 3) eine Lösung (zusätzlich zu allen ihren Wiederholungen):

</td></td></td></td></td></tr></tr></Tisch>

Probeskizze der Unentscheidbarkeit

Der allgemeinste Beweis für die Unentscheidbarkeit von PCP beschreibt ein Beispiel von PCP, der die Berechnung einer Maschine von Turing auf einem besonderen Eingang vortäuschen kann. Ein Match wird nur vorkommen, wenn der Eingang durch die Maschine von Turing akzeptiert würde. Weil entscheidend, ob eine Maschine von Turing akzeptieren wird, ein Eingang ein grundlegendes unentscheidbares Problem ist, kann PCP nicht auch entscheidbar sein. Die folgende Diskussion basiert auf dem Lehrbuch von Michael Sipser Einführung in die Theorie der Berechnung.

Ausführlicher besteht die Idee darin, dass die Schnur entlang der Spitze und dem Boden eine Berechnungsgeschichte der Maschinenberechnung von Turing sein wird. Das bedeutet, dass es eine Schnur verzeichnen wird, die den anfänglichen Staat beschreibt, der von einer Schnur gefolgt ist, die den folgenden Staat und so weiter beschreibt, bis es mit einer Schnur endet, die einen akzeptierenden Staat beschreibt. Die Zustandschnuren werden durch ein Separator-Symbol (gewöhnlich schriftlich #) getrennt. Gemäß der Definition einer Maschine von Turing besteht der volle Staat der Maschine aus drei Teilen:

• Der aktuelle Inhalt des Bandes.
• Der aktuelle Staat der Zustandsmaschine, die den Band-Kopf bedient.
• Die aktuelle Position des Bandes geht auf dem Band.

Obwohl das Band ungeheuer viele Zellen hat, wird nur ein begrenztes Präfix von diesen nichtleer sein. Wir schreiben diese als ein Teil unseres Staates nieder. Um den Staat der begrenzten Kontrolle zu beschreiben, schaffen wir neue Symbole, hat q durch q für jeden der ZustandsmaschinenK-Staaten etikettiert. Wir fügen das richtige Symbol in die Schnur ein, die den Inhalt des Bandes an der Position des Band-Kopfs dadurch beschreibt, sowohl die Band-Hauptposition als auch den aktuellen Staat der begrenzten Kontrolle anzeigend. Für das Alphabet {0,1} könnte ein typischer Staat etwas schauen wie:

101101110q00110.

Eine einfache Berechnungsgeschichte würde dann etwas wie das schauen:

q101#1q01#11q1#1q10.

Wir brechen mit diesem Block auf, wo x die Eingangsschnur ist und q der Anfang-Staat ist:

Die Spitze beginnt "Verkleidung" des Bodens durch einen Staat, und behält diesen Zeitabstand bis zur wirklichen Endbühne. Dann für jedes Symbol im Band-Alphabet, sowie # haben wir einen "Kopie"-Block, der es unmodifiziert von einem Staat bis das folgende kopiert:

Wir haben auch einen Block für jeden Positionsübergang, den die Maschine machen kann, sich zeigend, wie das Band Bewegungen anführt, wie sich der Endzustand ändert, und was mit den Umgebungssymbolen geschieht. Zum Beispiel hier ist der Band-Leiter über 0 in staatlichen 4, und schreibt dann 1 und bewegt Recht, sich zu staatlichen 7 ändernd:

Schließlich, wenn die Spitze einen akzeptierenden Staat erreicht, braucht der Boden eine Chance, schließlich aufzuholen, um das Match zu vollenden. Um das zu erlauben, erweitern wir die Berechnung, so dass sobald ein akzeptierender Staat erreicht wird, wird jeder nachfolgende Maschinenschritt ein Symbol in der Nähe vom Band-Kopf veranlassen, einer nach dem anderen zu verschwinden, bis zu niemandem bleiben. Wenn q ein akzeptierender Staat ist, können wir das mit den folgenden Übergang-Blöcken, wo vertreten eines Band-Alphabet-Symbols zu sein:

</td></td></tr></Tisch>

Es gibt mehrere Details, um, solcher als befassend mit Grenzen zwischen Staaten gut zu laufen, sicherstellend, dass unser anfänglicher Ziegel zuerst im Match und so weiter geht, aber das zeigt die allgemeine Idee davon, wie ein statisches Ziegel-Rätsel eine Maschinenberechnung von Turing vortäuschen kann.

Varianten

Viele Varianten von PCP sind betrachtet worden. Ein Grund besteht darin, dass, wenn man versucht, Unentscheidbarkeit von einem neuen Problem zu beweisen, indem man von PCP abnimmt, es häufig geschieht, dass die erste Verminderung, die man findet, nicht von PCP selbst, aber von einer anscheinend schwächeren Version ist.

• Die Bedingung, dass das Alphabet mindestens zwei Symbole hat, ist erforderlich, da das Problem entscheidbar ist, wenn nur ein Symbol hat.
• Eine einfache Variante soll n, die Zahl von Ziegeln befestigen. Dieses Problem ist entscheidbar, wenn n  2, aber unentscheidbar für n  7 bleibt. Es ist unbekannt, ob das Problem für 3  n  6 entscheidbar ist.
• Das kreisförmige Postähnlichkeitsproblem' fragt, ob Indizes solch gefunden werden können, dass und verbundene Wörter sind, d. h., sind sie gleiche modulo Folge. Diese Variante ist unentscheidbar.
• Eine der wichtigsten Varianten von PCP ist das begrenzte Postähnlichkeitsproblem', das fragt, ob wir ein Match finden können, das nicht mehr als k Ziegel einschließlich wiederholter Ziegel verwendet. Eine Suche der rohen Gewalt behebt das Problem rechtzeitig O (2), aber das kann schwierig sein zu übertreffen, da das Problem NP-complete ist. Verschieden von einigen NP-complete Problemen wie der boolean satisfiability Problem, wie man auch zeigte, war eine kleine Schwankung des begrenzten Problems für RNP abgeschlossen, was bedeutet, dass es hart bleibt, selbst wenn die Eingänge aufs Geratewohl gewählt werden (es ist durchschnittlich zu Ende hart gleichförmig hat Eingänge verteilt).
• Eine andere Variante von PCP wird das gekennzeichnete Postähnlichkeitsproblem genannt' in dem jeder u mit einem verschiedenen Symbol und jedem v beginnen muss, muss auch mit einem verschiedenen Symbol beginnen. Halava, Hirvensalo und de Wolf haben gezeigt, dass diese Schwankung in der Exponentialzeit entscheidbar ist. Außerdem haben sie gezeigt, dass, wenn diese Voraussetzung ein bisschen gelöst wird, so dass sich nur die Präfixe-Buchstaben zwei (das so genannte 2 gekennzeichnete Postähnlichkeitsproblem) unterscheiden müssen, das Problem unentscheidbar wieder wird.
• Das Posteinbetten-Problem ist eine andere Variante, wo man für solche Indizes schaut, der ein (gestreutes) Subwort dessen ist. Diese Variante ist seitdem leicht entscheidbar, wenn einige Lösungen, insbesondere eine Länge bestehen, besteht eine Lösung. Interessanter ist das Regelmäßige Posteinbetten-Problem, eine weitere Variante, wo man für Lösungen schaut, die einer gegebenen regelmäßigen Sprache (vorgelegt, z.B, unter der Form eines regelmäßigen Ausdrucks auf dem Satz) gehören. Das Regelmäßige Posteinbetten-Problem ist noch entscheidbar, aber, wegen der zusätzlichen regelmäßigen Einschränkung, hat es eine sehr hohe Kompliziertheit, die jeden beherrscht, multiplizier rekursive Funktion.

Außenverbindungen

• Eitan M. Gurari. Eine Einführung in die Theorie der Berechnung, das Kapitel 4, das Ähnlichkeitsproblem des Postens. Ein Beweis der Unentscheidbarkeit von PCP auf einer Generalisation von Grammatiken ohne Zusammenhänge gestützt.
• Online-PHP basierter PCP Solver
• PCP ZUHAUSE