If I show that a language $L$ is contained in $\textbf{P}$ and $\textbf{NP}$ and I know that the language is $\textbf{NP}$-complete, why did I proof that $\textbf{P} = \textbf{NP}$?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ If an NP-complete problem is solvable in polynomial time, then by definition NP=P. Check other questions on the same topic. $\endgroup$ – Pål GD Jan 24 '19 at 10:10
-
$\begingroup$ I suggest going over the basic definitions of completeness and checking out other related questions on the site, such as the one mentioned here in the comments. $\endgroup$ – Dean Gurvitz Jan 24 '19 at 10:31
Add a comment
|
$\begingroup$
$\endgroup$
Because you have then showed that $L$ is an $\textbf{NP}$-complete language which, since $L \in \textbf{P}$, is decidable in poly-time. Since any other language $L' \in \textbf{NP}$ is efficiently reducible to $L$ (because of $\textbf{NP}$-completeness), $L' \in \textbf{P}$ as well. It follows that $\textbf{NP} \subseteq \textbf{P}$ (and the other inclusion is trivial).
