Cesko.wiki Postův korespondenční problém
Author
Albert FloresPostů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| , pro všechny i. Nikdy tedy nebude délka |\alpha| rovna |\beta|.