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

597 Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST ANSWER

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