94/122

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