\begin{frame}{Bounded Tiling Problem is NP-complete}
  \begin{block}{Proof continued\ldots}
    Then, for input $x = a_1\cdots a_k$ and with the indicated starting row:
    \begin{talign}
      \alert{\text{$n\times n$ field can be tiled \quad$\iff$\quad $x \in L(M)$}}
    \end{talign}
    \pause
    Every tiling simulates a computation of $M$ on input $x$.
    \pause\medskip
    
    The computation takes at most $p(k)$ steps.
    \pause\medskip
    
    So the \alert{computation fills only $p(k) < n$ rows of the tiling}.
    \pause\medskip

    Hence, the $n \times n$ tiling can only be completed using
    \begin{center}
      \begin{tikzpicture}[default,nodes={rectangle}]
        \tilew{7}{0}{$q,\!c$}{}{$q,\!c$}{}
      \end{tikzpicture}
    \end{center}
    which exists only for \alert{$q \in F$}.
    \pause\medskip

    Tiling can be finished \\
    \ \hfill$\iff$ $M$ has an accepting computation for input $x$.
  \end{block}
  \vspace{10cm}
\end{frame}