$P = NP\text{ if and only if } \exists p \in NP-\text{ complete such that } p \in P$

141 Views Asked by At

$$P = NP\text{ if and only if } \exists p \in NP-\text{ complete such that } p \in P$$

Is this statement true? I can prove the first direction $\rightarrow$ but I have difficulties in showing that, supposing $\exists p \in NP-\text{ complete such that } p \in P$, this implies $P = NP$.

1

There are 1 best solutions below

3
On BEST ANSWER

The definition of $NP$-complete is

$p$ is $NP$-complete iff any $NP$ problem may be reduced to $p$ in polynomial time

(at least for the purposes of this question). If any $NP$-problem may be reduced to $p$ in polynomial time, and $p\in P$, what does that say about all $NP$-problems?