If a NP-complete problem is not in P, then all NP-complete problems are not in P?

$\begingroup$

It is clear to me that if a NP-Hard problem is solvable in P, then all NP-Hard problem (which include NP-Complete problems) are solvable in P.

But, is it also the case that if a NP-Complete problem is ever proven to be not solvable in P, then all NP-Complete problems will not be solvable in P?

$\endgroup$ 0

1 Answer

$\begingroup$

If we assume that there is $NP$-Complete problem lets say $p_1$ that's solvable in polynomial time, and another $NP$-Complete problem $p_2$ that's not solvable in polynomial time then we can reduce $p_2$ to $p_1$ in polynomial time and solve it in polynomial time, which is contradiction to the fact that $p_2$ is not in $P$. Or looking at it in another way if there's $NP$-Complete problem in $P$, then $P=NP$, so it would be impossible for any $NP$ problem to be unsolvable in polynomial time.

So this implies that if we could prove that there's an $NP$-Complete problem that's not in $P$, then all $NP$-complete problems are not in $P$.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy