15/122

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