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

  Intuitively a problem is in NP if:
  \item every instance has a finite set of possible solutions,
  \item correctness of a solution can be checked in polynomial time\!\!

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