Problembeschreibung

Beim PCP geht es darum, aus mehreren geordneten Paaren von Wortfragmenten eine Folge zu finden, die jeweils zwei gleiche Wortketten erzeugt. Das Problem ist sehr komplex, bei drei Wortpaaren mit Alphabet {0,1} und Wortfragmenten mit Länge kleiner gleich 3 kann die minimale Lösungsfolge grösser als 50 sein.