# Is this possible when it comes to the relations of P, NP, NP-Hard and NP-Complete?

I saw an image that describes the relations of P, NP, NP-Hard and NP-Complete which look like this :

https://en.wikipedia.org/wiki/NP-hardness#/media/File:P_np_np-complete_np-hard.svg

I wonder if the following is possible ? Which means, P = NP, but not all of them are in NP-Hard :

Edit : I want to add this : I'm not here to say if the original image is wrong or right, I'm just here to ask a question if my image contains a possible situation. In other words, is it correct to assume that all 3 images are possible ?

Actually, your version is correct and Wikipedia's is wrong! (Except that it has a tiny disclaimer at the bottom.)

If $$\mathrm{P}=\mathrm{NP}$$, Wikipedia claims that every problem in $$\mathrm{P}$$ is $$\mathrm{NP}$$-complete. However, this is not true: in fact, every problem in $$\mathrm{P}$$ would be $$\mathrm{NP}$$-complete, except for the trivial languages $$\emptyset$$ and $$\Sigma^*$$.

You can't many-one reduce any nonempty language $$L$$ to $$\emptyset$$, because a many-one reduction must map "yes" instances of $$L$$ to "yes" instances of $$\emptyset$$, but $$\emptyset$$ has no "yes" instances. Similarly, you can't reduce to $$\Sigma^*$$ because there's nothing to map the "no" instances to. However, if $$\mathrm{P}=\mathrm{NP}$$, then every other language in $$\mathrm{P}$$ is $$\mathrm{NP}$$-complete, since you can solve the language in the reduction.

So, just to make it explicit:

• your diagram is correct;
• Wikipedia's isn't (unless you read the tiny disclaimer);
• the area you've labelled "$$\mathrm{P}$$, $$\mathrm{NP}$$" contains the two languages $$\emptyset$$ and $$\Sigma^*$$, and nothing else;
• the area you've labelled "$$\mathrm{P}$$, $$\mathrm{NP}$$-complete" contains every other language in $$\mathrm{P}$$ and nothing else.
• "Actually, your version is correct and Wikipedia's is wrong!" It looks like that is a harsh judgement on Wikipedia's image with attached explanation while lenient on asker's image. The area labelled "P, NP" should be the full circle just as the area labelled "NP-hard" should mean the full parabolic area. The label "P, NP-complete" should better be "NP-complete". May 13, 2019 at 18:46
• It would be great if you can include a completely correct image that is least susceptible to wrong understanding. May 13, 2019 at 18:47