Unäres PCP

Das unäre PCP ist der Spezialfall des PCP, bei dem das Alphabet nur aus einem Zeichen besteht ($|\mathrm{\Sigma }|=1$). In diesem Fall ist das Problem entscheidbar, da es darauf hinausläuft zu prüfen, ob sich die Längendifferenzen $(|x_i|-|y_i|)$ linear zur Null kombinieren lassen.