\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}