\begin{frame}{Satisfiability Problem is NP-complete}
  \begin{block}{Theorem of Cook}
    The satisfiability problem in propositional logic is NP-complete.
  \end{block}
  \pause 
  
  \begin{block}{Proof}
    We give a polynomial-time reduction 
    from the bounded tiling problem
    to the satisfiability problem.
    \pause\medskip
    
    Given
    \begin{itemize}\setlength{\itemsep}{0pt}
      \item a set $T$ of tile types,
      \item a number $n$,
      \item a first row of tiles $t_1 \cdots t_n$. 
    \end{itemize}
    \pause\medskip

    We create a satisfiability problem as follows.
    \pause\medskip
    
    We introduce Boolean variables \alert{$x_{r c t}$ for $1 \leq r, c \leq n$ and $t \in T$}.
    \smallskip
    
    Intention: $x_{r c t}  = \mathtt{true}$ $\iff$ tile of type $t$ at row $r$ and column $c$.
    \pause\medskip
    
    
    \hfill\textcolor{gray}{continued on the next slide\ldots}
  \end{block}
\end{frame}