Beispiel 3 (PCP): Gegeben ist eine Liste von Wort-Paaren. Gesucht ist eine Folge (von Kopien dieser Paare), bei der die Verkettung alle linken Seiten das gleiche Wort ergibt wie die Verkettung aller rechten Seiten.
Beispiele:
Das linke hat kürzeste Lösung 
.
Aufgabe: finde Lösung für das rechte
(es gibt eine).
Jetzt ist der Suchraum (alle Folgen) gar nicht beschränkt (die Folgen können beliebig lang sein).
Tatsächlich ist PCP algorithmisch unlösbar! (Es gibt keinen Algorithmus, der für jede Liste von Paaren korrekt entscheidet, ob die Aufgabe eine Lösungsfolge besitzt.)