19/110
\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}