Wissenschaftssommer 2008

Das Postsche Korrespondenzproblem (PCP)

Die Aufgabe(n):

Grundaufgabe: Vorgegeben sind Paare von Bausteinen. Man soll daraus zwei Ketten legen (oben und unten), die zueinander passen und übereinstimmende Farbfolgen besitzen.
Instanzen: einige leichte lösbare, einige schwere lösbare , eine Instanz, bei der man rechnen muß
Ergänzungen: Beweise, daß die Aufgabe für die folgenden Bausteinpaare nicht lösbar ist (einige Beispiele)

Mathematischer Hintergrund

Die Frage, ob es für eine gegebene Menge von Bausteinpaaren eine Lösung gibt, ist das Postsche Korrespondenzproblem, benannt nach dem Mathematiker Emil Post.
Diese Frage ist nicht algorithmisch lösbar. Das Problem ist unentscheidbar. Wenn man einer Instanz durch Probieren lösen möchte, kann man nicht vorhersagen, wie lange man probieren muß.
Die Unentscheidbarkeit kann man wie folgt einsehen: Wir nennen den nicht überdeckten Teil der einen Kette die '(aktuelle) Differenz'. Man kann die Rechnung einer Turingmaschine so simulieren, daß die Bandinhalte als Differenzen einer PCP-Instanz auftreten. Damit folgt aus der Unentscheidbarkeit des Halteproblems. die Unentscheidbarkeit des PCP.
Daraus folgt weiterhin, daß diese Funktion nicht berechenbar ist: f(n,w) = maximale Länge einer kürzesten Lösung eines PCP aus n Paaren mit Bausteinen der Breite kleiner gleich w. Genauer: diese Funktion wächst schneller als jede berechenbare Funktion. Das erkennt man daran, daß bereits für kleine Argumente recht große Funktionswerte erreicht werden. Über die Jagd nach solchen Werten berichtet [2].
Es ist möglich, alle lösbaren PCP-Instanzen durch einen Algorithmus aufzuzählen: man probiert für die erste Instanz alle Ketten der Länge 1, dann für die 2. Instanz alle Ketten der Länge 1, dann f ür die 1. Instanz alle der Länge 2, dann f ür die 3. Instanz alle Ketten der Länge 1 usw. Das PCP ist damit in RE (rekursiv aufzählbare Mengen) und sogar vollständig in RE.

Anwendungen

Über die praktischen Folgen der Unentscheidbarkeit des Halteproblems: siehe die Beschreibung des Parkettierungs-Problems.
Die Bedeutung des PCP ist vor allem eine innermathematische: die Unentscheidbarkeit vieler Probleme aus dem Bereich der Logik und der formalen Sprachen folgt recht leicht aus der Unentscheidbarkeit des PCP. Es ist damit ein sehr nützliches Hilfsmittel. Die Frage, ob bestimmte Ketten von Symbolen zusammenpassen, stellt sich auch in der Biologie bei der Analyse von DNA-Strängen. Beim DNA-Computing nutzt man das aus, um Algorithmen mit Hilfe biologischer Substanzen und Vorgänge auszuführen.

Komplexitätsklasse: RE
Selber Ausprobieren:Hier!
Quellen / Fußnoten: [1] Richard J. Lorenz: Creating Difficult Instances of the Post Correspondence Problem, Computers and Games 2000, LNCS 2063, p. 214–228.
[2] Heiko Stamer: PCP@Home, http://www.theory.informatik.uni-kassel.de/˜stamer/pcp/

© HTWK