\begin{frame}{Problems in NP}
  \begin{goal}{}
    Recall, that the language corresponding to a decision problem consists of
    words representing instances of the problem for which the answer is \emph{yes}. 
  \end{goal}
  \pause\medskip

  Intuitively a problem is in NP if:
  \begin{itemize}
  \item every instance has a finite set of possible solutions,
  \item correctness of a solution can be checked in polynomial time\!\!
  \end{itemize}
  \pause\smallskip

  \begin{minipage}{.75\textwidth}
    \begin{exampleblock}{}
      The question whether the \emph{travelling salesman problem}
      has a solution of length $\le k$ is in NP.
    \end{exampleblock}
    \mpause[1]{
    \begin{exampleblock}{}
      \emph{Satisfiability in propositional logic} is in NP.
    \end{exampleblock}
    }\mpause{
    \begin{exampleblock}{}
      The questions if a number is \emph{not prime} is in NP.
    \end{exampleblock}
    }
  \end{minipage}
  \begin{minipage}{.24\textwidth}
    \hfill \includegraphics[height=20mm]{images/salesman.jpg}
  \end{minipage}
  \smallskip
  
  \mpause{
    Surprisingly, last question in P. (Agrawal, Kayal, Saxena, 2002)
  }
  \bigskip
\end{frame}