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