Postův korespondenční problém

Instance \pojem{Postova korespondenčního problému (PCP)} jsou dva seznamy slov nad abecedou $\Sigma$ značené $A=w_1,w_2,\ldots, w_k$ a $B=x_1,x_2,\ldots, x_k$ stejné délky $k$. Pro každé $i$, dvojice $(w_i,x_i) $ se nazývá \pojem{odpovídající} dvojice.

Instance PCP \pojem{má řešení}, pokud existuje posloupnost jednoho či více přirozených čísel ${i_1}, {i_2}, \ldots, {i_m}$ tak že $w_{i_1}, w_{i_2}, \ldots, w_{i_m}=x_{i_1}, x_{i_2}, \ldots, x_{i_m} $ tj. dostaneme stejné slovo.
V tom případě říkáme, že posloupnost ${i_1}, {i_2}, \ldots, {i_m}$  \pojem{je řešení}.

\pojem{Postův korespondenční problém} je: Pro danou instanci PCP, rozhodněte, zda má řešení.

» Slovník pojmů (ve vývoji)