Otdfbt

Multi tool use

Binary Search in C++17

What are the real benefits of using Salesforce DX?

Employer demanding to see degree after poor code review

Which is the common name of Mind Flayers?

Adding spaces to string based on list

Is the field of q-series 'dead'?

Image processing: Removal of two spots in fundus images

What is the object moving across the ceiling in this stock footage?

Why did David Cameron offer a referendum on the European Union?

the meaning of 'carry' in a novel

Would jet fuel for an F-16 or F-35 be producible during WW2?

Does the unit of measure matter when you are solving for the diameter of a circumference?

Compactness of finite sets

Why does Mjolnir fall down in Age of Ultron but not in Endgame?

How to use Palladio font in text body but Computer Modern for Equations?

Writing with dry erase marker on Shabbos, is it permitted?

Should breaking down something like a door be adjudicated as an attempt to beat its AC and HP, or as an ability check against a set DC?

Are these reasonable traits for someone with autism?

Is the Indo-European language family made up?

Where have Brexit voters gone?

What is the largest (size) solid object ever dropped from an airplane to impact the ground in freefall?

Defining the standard model of PA so that a space alien could understand

Crossing US border with music files I'm legally allowed to possess

Is CD audio quality good enough?

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

If P = NP, why does P = NP = NP-Complete?Proving NP-Completeness by reductionIs this simple problem NP-complete?Decisional problems vs Optimization problems : NP-COMPLETE vs NP-HARDIs an NP-hard problem which is in NP is NP-complete?What is meant by problems not in NP but in NP hard?Proof that AND-OR graph decision problem is NP-hardIs this language NP Hard?“Fuzzy” Chinese Remainder Theorem NP-hard?Is this reduction from 3D-MATCHING to PATH SELECTION invalid?NP-Hard on Complete Graphs

7

2

$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

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 ?

np-complete np-hard np

share|cite|improve this question

edited May 13 at 19:08

Frank

asked May 13 at 17:19

FrankFrank

1364

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Possible duplicate of If P = NP, why does P = NP = NP-Complete?
  $endgroup$
  – Jules Lamur
  May 14 at 0:20
  

  
  
  
  

add a comment | 

7

2

$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

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 ?

np-complete np-hard np

share|cite|improve this question

edited May 13 at 19:08

Frank

asked May 13 at 17:19

FrankFrank

1364

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Possible duplicate of If P = NP, why does P = NP = NP-Complete?
  $endgroup$
  – Jules Lamur
  May 14 at 0:20
  

  
  
  
  

add a comment | 

$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

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 ?

np-complete np-hard np

share|cite|improve this question

edited May 13 at 19:08

Frank

asked May 13 at 17:19

FrankFrank

1364

$endgroup$

share|cite|improve this question

edited May 13 at 19:08

Frank

asked May 13 at 17:19

FrankFrank

1364

share|cite|improve this question

edited May 13 at 19:08

Frank

asked May 13 at 17:19

FrankFrank

1364

asked May 13 at 17:19

FrankFrank

1364

asked May 13 at 17:19

FrankFrank

1364

1 Answer
1

active

oldest

votes

12

$begingroup$

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

If $mathrmP=mathrmNP$, Wikipedia claims that every problem in $mathrmP$ is $mathrmNP$-complete. However, this is not true: in fact, every problem in $mathrmP$ would be $mathrmNP$-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 $mathrmP=mathrmNP$, then every other language in $mathrmP$ is $mathrmNP$-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 "$mathrmP$, $mathrmNP$" contains the two languages $emptyset$ and $Sigma^*$, and nothing else;


• the area you've labelled "$mathrmP$, $mathrmNP$-complete" contains every other language in $mathrmP$ and nothing else.

share|cite|improve this answer

answered May 13 at 17:55

David RicherbyDavid Richerby

72.1k16111201

$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
  
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f109308%2fis-this-possible-when-it-comes-to-the-relations-of-p-np-np-hard-and-np-complet%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

12

$begingroup$

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

If $mathrmP=mathrmNP$, Wikipedia claims that every problem in $mathrmP$ is $mathrmNP$-complete. However, this is not true: in fact, every problem in $mathrmP$ would be $mathrmNP$-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 $mathrmP=mathrmNP$, then every other language in $mathrmP$ is $mathrmNP$-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 "$mathrmP$, $mathrmNP$" contains the two languages $emptyset$ and $Sigma^*$, and nothing else;


• the area you've labelled "$mathrmP$, $mathrmNP$-complete" contains every other language in $mathrmP$ and nothing else.

share|cite|improve this answer

answered May 13 at 17:55

David RicherbyDavid Richerby

72.1k16111201

$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
  
  

  
  
  
  

add a comment | 

12

$begingroup$

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

If $mathrmP=mathrmNP$, Wikipedia claims that every problem in $mathrmP$ is $mathrmNP$-complete. However, this is not true: in fact, every problem in $mathrmP$ would be $mathrmNP$-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 $mathrmP=mathrmNP$, then every other language in $mathrmP$ is $mathrmNP$-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 "$mathrmP$, $mathrmNP$" contains the two languages $emptyset$ and $Sigma^*$, and nothing else;


• the area you've labelled "$mathrmP$, $mathrmNP$-complete" contains every other language in $mathrmP$ and nothing else.

share|cite|improve this answer

answered May 13 at 17:55

David RicherbyDavid Richerby

72.1k16111201

$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
  
  

  
  
  
  

add a comment | 

$begingroup$

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

If $mathrmP=mathrmNP$, Wikipedia claims that every problem in $mathrmP$ is $mathrmNP$-complete. However, this is not true: in fact, every problem in $mathrmP$ would be $mathrmNP$-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 $mathrmP=mathrmNP$, then every other language in $mathrmP$ is $mathrmNP$-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 "$mathrmP$, $mathrmNP$" contains the two languages $emptyset$ and $Sigma^*$, and nothing else;


• the area you've labelled "$mathrmP$, $mathrmNP$-complete" contains every other language in $mathrmP$ and nothing else.

share|cite|improve this answer

answered May 13 at 17:55

David RicherbyDavid Richerby

72.1k16111201

$endgroup$

share|cite|improve this answer

answered May 13 at 17:55

David RicherbyDavid Richerby

72.1k16111201

answered May 13 at 17:55

David RicherbyDavid Richerby

72.1k16111201

answered May 13 at 17:55

David RicherbyDavid Richerby

72.1k16111201