# Why does showing that a NP problem is not NP-complete implies P$\neq$NP?

I found in this answer that if a problem is shown to be NP but not NP-complete then P$$\neq$$NP. What is the argument to prove this statement?

• The answer says that a problem in NP is proved to not be NP-complete. Such a problem can only exist if P $\neq$ NP. Commented Dec 1, 2022 at 21:53
• @pål-gd Yes, and I'm asking why is that so. Commented Dec 1, 2022 at 21:59

This statement is false.

It is already known that the empty problem and the universal problem are in $$\mathsf{NP}$$ and are not $$\mathsf{NP}$$-complete (not even $$\mathsf{P}$$-complete).

However, what is true is that if $$A\in \mathsf{NP}$$ is not one of the two problems above, then $$A$$ is $$\mathsf{P}$$-hard. To prove this result, consider $$a\in A$$ and $$b \notin A$$ (those exist because $$A$$ is neither the empty nor the universal language). Then for any $$B\in\mathsf{P}$$, you can create the following function: $$f : x\mapsto \left\{ \begin{array}{ll} a& \text{if }x\in B\\b&\text{otherwise}\end{array}\right.$$ Since $$B\in \mathsf{P}$$, $$f$$ is computable in polynomial time. Given the definition of $$f$$, $$a$$ and $$b$$, it is clear that: $$x\in B \Leftrightarrow f(x)\in A$$ That means that there is a polynomial time many-one reduction from $$B$$ to $$A$$.

Now if such a language $$A$$ is not $$\mathsf{NP}$$-complete, then $$\mathsf{P}\neq \mathsf{NP}$$ (because $$A$$ is $$\mathsf{P}$$-hard and not $$\mathsf{NP}$$-hard).

• If P=NP then NP-complete and P-complete are the same. All P problems are P-complete (under polynomial-time reductions). Therefore if a problem in NP(=P) is not NP-complete we have a contradiction and P$\neq$NP. (All these with the exception of the empty and universal language) Commented Dec 2, 2022 at 23:50
• Yes, that's it. Commented Dec 3, 2022 at 9:26

If a problem X is NP-complete that means by definition that I can take any problem Y in NP, and for every instance of Y I can construct an instance of X so that solving X allows me to solve Y in polynomial time.

Now assume P = NP. Then Y is in P, so I can solve it in polynomial time anyway - without having to construct an instance of X at all, or by constructing one and ignoring it completely when I solve the instance of Y. That means any problem in P is in NP and is NP-complete. NP complete just doesn't mean much; if P = NP then P = NP-complete.

Now we reverse the logic: If P = NP then every problem in NP is NP-complete, so if there is a problem in NP that is not NP-complete then P ≠ NP.

(And there is a problem: There are two problems (the empty problem and the complete problem) where all instances have the same answer, either all instances have the answer NO or all instances have the answer YES, so you cannot find two instances with different answers and things break down).