HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thistherelationshardpossiblecompletecomeswhenand

Problem

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 ?

Solution

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.

Context

StackExchange Computer Science Q#109308, answer score: 12

Revisions (0)

No revisions yet.