\begin{frame}{NP-completeness and P = NP?}
  \begin{block}{Theorem}
    If an NP-complete language $L$ is also in $P$, then $\text{P} = \text{NP}$. 
  \end{block}
  \pause
  
  \begin{proof}
    Assume that $L$ is NP-complete and in P.
    \pause\medskip
    
    Let $L' \in \text{NP}$.
    \pause\medskip

    As $L$ is NP-complete, there is a polynomial-time reduction $f$ with
    \begin{talign}
      x \in L' \iff f(x)\in L
    \end{talign}
    \pause
    Since $L \in \text{P}$, we can compute $f(x) \in L$ in polynomial time.
    \pause\medskip

    Thus $x \in L'$ can be decided in polynomial time. 
    \medskip
    
    Hence $L' \in \text{P}$.
  \end{proof}
  \pause
  
  \begin{goal}{}
    For proving $\text{P} = \text{NP}$ it suffices to show that
    one NP-complete problem can be solved in deterministic polynomial time.
  \end{goal}
\end{frame}

\subsection{The Class co-NP}

\themex{co-NP}