Postův korespondenční problém

Postův korespondenční problém (PCP) je nerozhodnutelný problém představený matematikem Emilem Postem v roce 1946. Problém je algoritmicky nerozhodnutelný. Redukce z PCP nebo jeho doplňku se používají k důkazům nerozhodnutelnosti.

Postův systém

Postův systém je tvořen neprázdným seznamem S dvojic neprázdných řetězců:

$S=\{(\alpha _{1},\beta _{1}),\,\ldots ,\,(\alpha _{k},\beta _{k})\}$, kde $k\geq 1$ a $\alpha _{i},\beta _{i}$ jsou řetězce nad nějakou abecedou, která obsahuje alespoň dva symboly (v případě abecedy s jedním symbolem je problém rozhodnutelný).

Řešením Postova systému je každá neprázdná posloupnost přirozených čísel I:

$I=\{i_{1},\,\ldots ,\,i_{m}\}$, kde $1\leq i_{j}\leq k$ a $m\geq 1$, pro kterou platí $\alpha _{i_{1}}\ldots \alpha _{i_{m}}=\beta _{i_{1}}\ldots \beta _{i_{m}}$.

Postův korespondenční problém je pak rozhodnout, zda pro daný konkrétní Postův systém existuje řešení či nikoli.

Příklady

Systém $S_{1}=\{(b,bbb),\,(babbb,ba),\,(ba,a)\}$ má řešení $I=\{2,\,1,\,1,\,3\}$ (babbb b b ba = ba bbb bbb a).

Systém $S_{2}=\{(ab,abb),\,(a,ba),\,(b,bb)\}$ řešení nemá, jelikož délka $|\alpha _{i}|<|\beta _{i}|$, pro všechny $i$. Nikdy tedy nebude délka $|\alpha |$ rovna $|\beta |$.