\begin{frame}{Bounded Tiling Problem is NP-complete}
  \begin{block}{Theorem}
    The bounded tiling problem is NP-complete.
  \end{block}
  \pause

  \begin{block}{Proof}
    \emph{First}, we argue that the bounded tiling problem is in NP.
    \pause\medskip
    
    We can construct a nondeterministic Turing machien that 
    \begin{itemize}
      \item guesses an $n \times n$ tiling, and
      \item afterwards checks whether the solution is correct.
    \end{itemize}
    Both steps can be done in polynomial time.
    \pause\medskip
    
    \emph{Second}, we show NP-completeness.
    \pause\medskip
    
    Let $M$ be a nondeterministic polynomial-time Turing machine.\\
    \pause
    Then $M$ has \alert{running time $p(k)$} for some polynomial $p(k)$.
    \pause\medskip
    
    We give a polynomial-time reduction of 
    \text{\alert{$x\in L(M)\,?$}}
    to the bounded tiling problem.
    \hfill\pause
    \textcolor{gray}{continued on the next slide\ldots}
  \end{block}
\end{frame}