\begin{frame}{Post's Correspondence Problem} \begin{block}{Post Correspondence Problem (PCP)} Given $n$ pairs of words: \begin{talign} \pair{w_1}{v_1},\;\ldots,\;\pair{w_n}{v_n} \end{talign} Are there indices $i_1,i_2\ldots,i_k$ ($k \ge 1$) s.t. \begin{talign} w_{i_1} w_{i_2} \cdots w_{i_k} ~~ = ~~ v_{i_1} v_{i_2} \cdots v_{i_k} ~~ ? \end{talign} \end{block} \pause \begin{exampleblock}{} \begin{itemize} \pause \item $\pair{1}{101},\pair{10}{00},\pair{011}{11}$ \tabto{6.7cm} \mpause[1]{\alert{solution $\seq{1,3,2,3}$}} \updatepause \item $\pair{110}{0},\pair{00}{1}$ \tabto{6.7cm} \mpause{\alert{no solution}} \updatepause \item $\pair{1}{111},\pair{10111}{10},\pair{10}{0}$ \tabto{6.7cm} \mpause{\alert{solution $\seq{2,1,1,3}$}} \updatepause \item $\pair{001}{0},\pair{01}{011},\pair{01}{101},\pair{10}{001}$ \tabto{6.7cm} \mpause{\alert{solution length 66}} \end{itemize} \end{exampleblock} \updatepause \begin{exampleblock}{PCP as decision problem} \begin{itemize} \item $\forestgreen{\text{PCP}} = \descsetexp{\seq{\pair{w_1}{v_1},\ldots,\pair{w_k}{v_k}}} {k\ge 1,\, w_i,v_i\text{ bin.\ words}} $ \item $\yesinstances = \descsetexp{i\in\forestgreen{\text{PCP}}}{\text{$i$ has a solution}}$ \end{itemize} \end{exampleblock} \end{frame}