\begin{frame}{Examples of NP-complete Problems}
  \begin{exampleblock}{}
    The question whether the \emph{travelling salesman problem} has a solution of length $\le k$
    is NP-complete.
  \end{exampleblock}
  \pause\medskip
  
  \begin{exampleblock}{}
    \emph{Satisfiability} for formulas of propositional logic is NP-complete.
  \end{exampleblock}
  \pause\medskip
  
  \begin{exampleblock}{}
    The question whether a graph contains a \emph{Hamiltonian cycle}
    (a cycle that visits each node exactly once) is NP-complete.
  \end{exampleblock}
  \pause\medskip
  
  \begin{exampleblock}{}
    The \emph{bounded tiling problem} is NP-complete.
  \end{exampleblock}
  \pause\medskip

  \ldots and many more questions
\end{frame}