Samræmingarverkefni Posts

Úr Wikipediu, frjálsa alfræðiritinu
Stökkva á: flakk, leita

Samræmingarverkefni Posts[1] er óleysanlegt ákvörðunarvandamál sem Emil Post lagði til árið 1946. Vandamálið gengur út á að taka tvo endanlega orðalista \alpha_{1}, \ldots, \alpha_{N} og \beta_{1}, \ldots, \beta_{N} úr einhverju stafrófi A sem inniheldur minnst tvö tákn og skilar röð af vísum (i_k)_{1 \le k \le K} þar sem K \ge 1 og  1 \le i_k \le N fyrir öll k svo að

\alpha_{i_1} \ldots \alpha_{i_K} = \beta_{i_1} \ldots \beta_{i_K}.

Tilvísanir[breyta]

  1. Algorithms, Logic, and Complexity Icelandic-english course dictionary