\begin{frame}{NP-completeness}
  \begin{block}{}
    Let $L_1 \subseteq \Sigma_1^*$ and $L_2 \subseteq \Sigma_2^*$ be decision problems (languages).
    \medskip
    
    Then $L_1$ is \emph{polynomial-time reducible} to $L_2$ if there exists
    a \emph{polynomial-time computable} function $f: \Sigma_1^* \to \Sigma_2^*$ such that:
    \begin{talign}
      x\in L_1 ~\iff~ f(x)\in L_2
    \end{talign}
  \end{block}
  \pause
  
  \begin{goal}{}
    To decide if $x \in L_1$, we can compute $f(x)$ and check $f(x) \in L_2$.
  \end{goal}
  So the problem $L_1$ is reduced to the problem $L_2$.
  \pause
  
  \begin{block}{}
    Let $f : \Sigma_1^* \to \Sigma_2^*$ and
    $g : \Sigma_2^* \to \Sigma_3^*$ 
    be polynomial-time reductions.\\
    The composition $g \circ f : \Sigma_1^* \to \Sigma_3^*$ 
    is a polynomial-time reduction.
  \end{block}
  \pause\medskip

  \begin{block}{NP-completeness}
    A language $L \in \text{NP}$ is \emph{NP-complete} if \alert{every language in NP}
    is polynomial time reducible to $L$.
  \end{block}
\end{frame}