If P=NP then how we can we say P=NP=NP-complete?
In wikipedia I found this diagram. I don't get how under the asumption p=np we get p=np=np-complete?
Answer
Not sure this is on topic for stack overflow (Theoretical Comp Sci), but NP-hard, as correctly visualized in the diagram is "the set of problems that are at least as hard as those in NP"; this includes problems that are worse than NP in one sense or another.
NP-complete problems are those problems in NP-hard that have a reducibility relationship with specific problems that are known to be in NP. Essentially, every problem that can be converted in polynomial time or better to a problem in NP-complete is just as hard as the others.
Here are a couple good snippets from CLRS that illustrate the issue:
The class NP consists of those problems that are “verifiable” in polynomial time. What do we mean by a problem being verifiable? If we were somehow given a "certificate” of a solution, then we could verify that the certificate is correct in time polynomial in the size of the input to the problem.
Informally, a problem is in the class NPC—and we refer to it as being NP-complete—if it is in NP and is as “hard” as any problem in NP.
A decidable language L is NP-complete if:
- L is in NP, and
- L' can be reduced to L in polynomial time for every L' in NP.
If a language L satisfies property 2, but not necessarily property 1, we say that L is NP-hard. We also define NPC to be the class of NP-complete languages.
(I may have the L' and L backwards there, the reducibility symbol is backwards from the way it is read in English.)
So what's the point? Well, you can just solve it with set theory: NP-complete is a subset of NP, and if P=NP, then NP-complete is a subset of P (in fact, they all become equal at that point, since you can solve any of them by first changing them to something your magic P-algorithm can work on). NP-hard still includes some NP-complete problems, but there are other problems outside, which are just hard.