\begin{frame}{Bounded Tiling Problem is NP-complete}
  \begin{block}{Proof continued\ldots (the starting row)}
    For \alert{input word $x = a_1\cdots a_k$} we choose \alert{$n = 2 p(k) + 1$}.\\
    \textcolor{gray}{(Assume $p(k) \ge k$, otherwise make it so.)}
    \medskip
    
    As first row we choose:
    \begin{center}
      \begin{tikzpicture}[default]
        \tilew{0}{0}{$\vphantom{W}\Box$}{}{}{}
        \node at (1.5,.5) {$\cdots$};
        \tilew{2}{0}{$\vphantom{W}\Box$}{}{}{}
        \tilew{3}{0}{$q_0,\!a_1$}{}{}{}
        \tilew{4}{0}{$a_2$}{}{}{}
        \node at (5.5,.5) {$\cdots$};
        \tilew{6}{0}{$a_k$}{}{}{}
        \tilew{7}{0}{$\vphantom{W}\Box$}{}{}{}
        \node at (8.5,.5) {$\cdots$};
        \tilew{9}{0}{$\vphantom{W}\Box$}{}{}{}
        
        \begin{scope}[-,thin,nodes={scale=.8}]
        \draw [decorate,decoration={brace,amplitude=5pt},xshift=0pt,yshift=0pt] (3,-0.1) -- (0,-0.1) node [midway,below] {$p(k)$};
        \draw [decorate,decoration={brace,amplitude=5pt},xshift=0pt,yshift=0pt] (10,-0.1) -- (4,-0.1) node [midway,below] {$p(k)$};
        \end{scope}
      \end{tikzpicture}\vspace{-1.5ex}
    \end{center}
    \pause
    Tiles for building the first row (for every $a \in \Sigma$):
    \begin{center}\vspace{-.5ex}
      \begin{tikzpicture}[default,nodes={rectangle}]
        \tilew{0}{0}{$\vphantom{W}\Box$}{}{}{}
        \tilew{2}{0}{$q_0,\!a$}{}{}{}
        \tilew{4}{0}{$a$}{}{}{}
      \end{tikzpicture}
    \end{center}
    \hfill\pause
    \textcolor{gray}{continued on the next slide\ldots}
  \end{block}
  \vspace{10cm}
\end{frame}