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$ 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$ Jan 24 '19 at 10:31

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).


Not the answer you're looking for? Browse other questions tagged or ask your own question.