2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Pål GD
    Commented Dec 1, 2022 at 21:53
  • $\begingroup$ @pål-gd Yes, and I'm asking why is that so. $\endgroup$
    – agimarco
    Commented Dec 1, 2022 at 21:59

2 Answers 2

4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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) $\endgroup$
    – agimarco
    Commented Dec 2, 2022 at 23:50
  • $\begingroup$ Yes, that's it. $\endgroup$
    – Nathaniel
    Commented Dec 3, 2022 at 9:26
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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