\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}