Postův korespondenční problém

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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.

Ř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[editovat | editovat zdroj]

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|.