# 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:

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