-1
$\begingroup$

This question already has an answer here:

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}$?

$\endgroup$

marked as duplicate by Pål GD, Derek Elkins, David Richerby complexity-theory Jan 24 at 10:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\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 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 at 10:31
4
$\begingroup$

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

$\endgroup$

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