7
$\begingroup$

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

enter image description here

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

enter image description here

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 ?

$\endgroup$
12
$\begingroup$

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.
$\endgroup$
  • 7
    $\begingroup$ "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". $\endgroup$ – Apass.Jack May 13 at 18:46
  • 13
    $\begingroup$ It would be great if you can include a completely correct image that is least susceptible to wrong understanding. $\endgroup$ – Apass.Jack May 13 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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