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