\begin{frame}{The Class co-NP}
  \begin{block}{}
    A problem $L$ is in \alert{co-NP} if the complement $\overline{L}$ is in NP.
  \end{block}
  In other words, the set of instances without solution is in NP.
  \pause\medskip
  
  \begin{exampleblock}{}
    The question whether a propositional formula is \emph{not} satisfiable is in co-NP.
  \end{exampleblock}
  \pause\bigskip\medskip

  \begin{alertblock}{}
    It is \alert{unknown} whether $\text{NP} = \text{co-NP}$. 
  \end{alertblock}
  \pause\smallskip

  \begin{exampleblock}{}
    It is unknown whether the satisfiability problem is in co-NP.
  \end{exampleblock}
  \pause

  The difficulty is that it has to be shown that a formula 
  evaluates to \texttt{false} for \emph{every} variable assignment.
  \pause\medskip
  
  \begin{block}{Theorem}
    If an NP-complete problem is in co-NP, then $\text{NP} = \text{co-NP}$.
  \end{block}
  
  Note that there are problems that are both in $\text{NP} \cap \text{co-NP}$.
  \bigskip
\end{frame}

\themex{Space Complexity}