Relation between Undecidable problems and NP-Hard











up vote
6
down vote

favorite
4












enter image description here



enter image description here



I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly.

And then, I realized that it is not certain where undecidable problems should be placed.

Did I draw the pictures correctly? (Are all the undecidable problems including the halting problem are NP-Hard when P=NP, and some of them are so when P≠NP?)

I asked this to professor, but he said that undecidable problems including the Halting problem are not NP Hard because they are not solvable, which is a contrast to many answers in Stack exchange.



And one more thing, when P≠NP, are there problems which are neither NP nor NP Hard? If so, are they undecidable problems too? (Highlighted with a blue line in the second picture)










share|cite|improve this question




















  • 1




    I disagree - NP-hardness does not require the set to be decidable. I think the confusion was that NP sets (including NP-complete sets) have to be decidable.
    – sdcvvc
    Dec 10 at 7:41















up vote
6
down vote

favorite
4












enter image description here



enter image description here



I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly.

And then, I realized that it is not certain where undecidable problems should be placed.

Did I draw the pictures correctly? (Are all the undecidable problems including the halting problem are NP-Hard when P=NP, and some of them are so when P≠NP?)

I asked this to professor, but he said that undecidable problems including the Halting problem are not NP Hard because they are not solvable, which is a contrast to many answers in Stack exchange.



And one more thing, when P≠NP, are there problems which are neither NP nor NP Hard? If so, are they undecidable problems too? (Highlighted with a blue line in the second picture)










share|cite|improve this question




















  • 1




    I disagree - NP-hardness does not require the set to be decidable. I think the confusion was that NP sets (including NP-complete sets) have to be decidable.
    – sdcvvc
    Dec 10 at 7:41













up vote
6
down vote

favorite
4









up vote
6
down vote

favorite
4






4





enter image description here



enter image description here



I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly.

And then, I realized that it is not certain where undecidable problems should be placed.

Did I draw the pictures correctly? (Are all the undecidable problems including the halting problem are NP-Hard when P=NP, and some of them are so when P≠NP?)

I asked this to professor, but he said that undecidable problems including the Halting problem are not NP Hard because they are not solvable, which is a contrast to many answers in Stack exchange.



And one more thing, when P≠NP, are there problems which are neither NP nor NP Hard? If so, are they undecidable problems too? (Highlighted with a blue line in the second picture)










share|cite|improve this question















enter image description here



enter image description here



I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly.

And then, I realized that it is not certain where undecidable problems should be placed.

Did I draw the pictures correctly? (Are all the undecidable problems including the halting problem are NP-Hard when P=NP, and some of them are so when P≠NP?)

I asked this to professor, but he said that undecidable problems including the Halting problem are not NP Hard because they are not solvable, which is a contrast to many answers in Stack exchange.



And one more thing, when P≠NP, are there problems which are neither NP nor NP Hard? If so, are they undecidable problems too? (Highlighted with a blue line in the second picture)







complexity-theory computability undecidability np-hard






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 10 at 6:41









Raphael

57.2k23139312




57.2k23139312










asked Dec 10 at 3:48









Riddle Aaron

404




404








  • 1




    I disagree - NP-hardness does not require the set to be decidable. I think the confusion was that NP sets (including NP-complete sets) have to be decidable.
    – sdcvvc
    Dec 10 at 7:41














  • 1




    I disagree - NP-hardness does not require the set to be decidable. I think the confusion was that NP sets (including NP-complete sets) have to be decidable.
    – sdcvvc
    Dec 10 at 7:41








1




1




I disagree - NP-hardness does not require the set to be decidable. I think the confusion was that NP sets (including NP-complete sets) have to be decidable.
– sdcvvc
Dec 10 at 7:41




I disagree - NP-hardness does not require the set to be decidable. I think the confusion was that NP sets (including NP-complete sets) have to be decidable.
– sdcvvc
Dec 10 at 7:41










2 Answers
2






active

oldest

votes

















up vote
8
down vote



accepted










I believe that this answer by Yuval Filmus all the questions you have asked.




If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$neq$NP. If $A$ is a set and $f_i$ reduces SAT to $A$ in polytime, then $f_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f_i$ to get a polytime algorithm for SAT.



We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.



The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f_i$ is infinite). We define $A$ on $f_i(s)$ so that $s in SAT$ iff $f_i(s) notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s in A$ iff $|s| in K$.



By construction, no polytime $f_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n in K$ (for $n geq 2$) by taking a majority of three strings of length $n$.




To summarize,




  1. Halting problem is NP-hard.

  2. If $Pne NP$, not all undecidable problems are NP-hard.

  3. If $P = NP$, all non-trivial sets are NP-hard.


The original answer had not addressed the last part of your question, namely, are there problems which are neither NP nor NP Hard? I will be lazy again and quote another answer, this time by Peter Shor.




There is a problem which is both NP-hard and in coNP if and only if NP = coNP.



If NP = coNP, than NP-complete problems (like 3-SAT) are both NP-hard and in coNP.



On the other hand, if any NP-hard problem is in coNP, then all problems in NP are reducible to it, so all problems in NP are in coNP so NP ⊆ coNP. Now, since the complement of NP is coNP, and vice versa, we also have coNP ⊆ NP. This means NP = coNP.



The question of whether NP = coNP is open, but most theoretical computer scientists do not think it is very likely.




So, assuming $NP ne coNP$, there exist problems that are decidable but neither in NP nor NP-hard. Note that we don't know that $NP = coNP$ implies $P = NP$. So this is a stronger assumption than the one you had suggested ($P ne NP$).






share|cite|improve this answer



















  • 1




    +1, I'd like to add that point 1 holds under the normal binary encoding of the halting problem; the unary encoding is not NP-hard, unless P=NP.
    – sdcvvc
    Dec 10 at 7:40










  • "not all undecidable problems are NP-hard" means that there are some undecidable problems are not in NP-hard, and that means P≠NP because if P=NP, all problems are NP-hard. So I think that we do not know whether "not all undecidable problems are NP-hard" before we solve P-NP problem. Am I correct?
    – Riddle Aaron
    Dec 10 at 7:55










  • @RiddleAaron That sounds right.
    – Alex Smart
    Dec 10 at 8:02


















up vote
2
down vote













Your second diagram seems to be claiming that (assuming $mathrm{P}=mathrm{NP}$), every $mathrm{NP}$-hard problem that is not $mathrm{NP}$-complete is undecidable. That's certainly not true. For example, by the time hierarchy theorem, we know that $mathrm{NEXP}supsetneqmathrm{NP}$. $mathrm{NEXP}$ is a set of decidable problems and it contains $mathrm{NP}$-hard problems that are not in $mathrm{NP}$.






share|cite|improve this answer





















    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    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',
    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


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f101316%2frelation-between-undecidable-problems-and-np-hard%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    8
    down vote



    accepted










    I believe that this answer by Yuval Filmus all the questions you have asked.




    If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$neq$NP. If $A$ is a set and $f_i$ reduces SAT to $A$ in polytime, then $f_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f_i$ to get a polytime algorithm for SAT.



    We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.



    The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f_i$ is infinite). We define $A$ on $f_i(s)$ so that $s in SAT$ iff $f_i(s) notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s in A$ iff $|s| in K$.



    By construction, no polytime $f_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n in K$ (for $n geq 2$) by taking a majority of three strings of length $n$.




    To summarize,




    1. Halting problem is NP-hard.

    2. If $Pne NP$, not all undecidable problems are NP-hard.

    3. If $P = NP$, all non-trivial sets are NP-hard.


    The original answer had not addressed the last part of your question, namely, are there problems which are neither NP nor NP Hard? I will be lazy again and quote another answer, this time by Peter Shor.




    There is a problem which is both NP-hard and in coNP if and only if NP = coNP.



    If NP = coNP, than NP-complete problems (like 3-SAT) are both NP-hard and in coNP.



    On the other hand, if any NP-hard problem is in coNP, then all problems in NP are reducible to it, so all problems in NP are in coNP so NP ⊆ coNP. Now, since the complement of NP is coNP, and vice versa, we also have coNP ⊆ NP. This means NP = coNP.



    The question of whether NP = coNP is open, but most theoretical computer scientists do not think it is very likely.




    So, assuming $NP ne coNP$, there exist problems that are decidable but neither in NP nor NP-hard. Note that we don't know that $NP = coNP$ implies $P = NP$. So this is a stronger assumption than the one you had suggested ($P ne NP$).






    share|cite|improve this answer



















    • 1




      +1, I'd like to add that point 1 holds under the normal binary encoding of the halting problem; the unary encoding is not NP-hard, unless P=NP.
      – sdcvvc
      Dec 10 at 7:40










    • "not all undecidable problems are NP-hard" means that there are some undecidable problems are not in NP-hard, and that means P≠NP because if P=NP, all problems are NP-hard. So I think that we do not know whether "not all undecidable problems are NP-hard" before we solve P-NP problem. Am I correct?
      – Riddle Aaron
      Dec 10 at 7:55










    • @RiddleAaron That sounds right.
      – Alex Smart
      Dec 10 at 8:02















    up vote
    8
    down vote



    accepted










    I believe that this answer by Yuval Filmus all the questions you have asked.




    If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$neq$NP. If $A$ is a set and $f_i$ reduces SAT to $A$ in polytime, then $f_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f_i$ to get a polytime algorithm for SAT.



    We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.



    The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f_i$ is infinite). We define $A$ on $f_i(s)$ so that $s in SAT$ iff $f_i(s) notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s in A$ iff $|s| in K$.



    By construction, no polytime $f_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n in K$ (for $n geq 2$) by taking a majority of three strings of length $n$.




    To summarize,




    1. Halting problem is NP-hard.

    2. If $Pne NP$, not all undecidable problems are NP-hard.

    3. If $P = NP$, all non-trivial sets are NP-hard.


    The original answer had not addressed the last part of your question, namely, are there problems which are neither NP nor NP Hard? I will be lazy again and quote another answer, this time by Peter Shor.




    There is a problem which is both NP-hard and in coNP if and only if NP = coNP.



    If NP = coNP, than NP-complete problems (like 3-SAT) are both NP-hard and in coNP.



    On the other hand, if any NP-hard problem is in coNP, then all problems in NP are reducible to it, so all problems in NP are in coNP so NP ⊆ coNP. Now, since the complement of NP is coNP, and vice versa, we also have coNP ⊆ NP. This means NP = coNP.



    The question of whether NP = coNP is open, but most theoretical computer scientists do not think it is very likely.




    So, assuming $NP ne coNP$, there exist problems that are decidable but neither in NP nor NP-hard. Note that we don't know that $NP = coNP$ implies $P = NP$. So this is a stronger assumption than the one you had suggested ($P ne NP$).






    share|cite|improve this answer



















    • 1




      +1, I'd like to add that point 1 holds under the normal binary encoding of the halting problem; the unary encoding is not NP-hard, unless P=NP.
      – sdcvvc
      Dec 10 at 7:40










    • "not all undecidable problems are NP-hard" means that there are some undecidable problems are not in NP-hard, and that means P≠NP because if P=NP, all problems are NP-hard. So I think that we do not know whether "not all undecidable problems are NP-hard" before we solve P-NP problem. Am I correct?
      – Riddle Aaron
      Dec 10 at 7:55










    • @RiddleAaron That sounds right.
      – Alex Smart
      Dec 10 at 8:02













    up vote
    8
    down vote



    accepted







    up vote
    8
    down vote



    accepted






    I believe that this answer by Yuval Filmus all the questions you have asked.




    If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$neq$NP. If $A$ is a set and $f_i$ reduces SAT to $A$ in polytime, then $f_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f_i$ to get a polytime algorithm for SAT.



    We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.



    The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f_i$ is infinite). We define $A$ on $f_i(s)$ so that $s in SAT$ iff $f_i(s) notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s in A$ iff $|s| in K$.



    By construction, no polytime $f_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n in K$ (for $n geq 2$) by taking a majority of three strings of length $n$.




    To summarize,




    1. Halting problem is NP-hard.

    2. If $Pne NP$, not all undecidable problems are NP-hard.

    3. If $P = NP$, all non-trivial sets are NP-hard.


    The original answer had not addressed the last part of your question, namely, are there problems which are neither NP nor NP Hard? I will be lazy again and quote another answer, this time by Peter Shor.




    There is a problem which is both NP-hard and in coNP if and only if NP = coNP.



    If NP = coNP, than NP-complete problems (like 3-SAT) are both NP-hard and in coNP.



    On the other hand, if any NP-hard problem is in coNP, then all problems in NP are reducible to it, so all problems in NP are in coNP so NP ⊆ coNP. Now, since the complement of NP is coNP, and vice versa, we also have coNP ⊆ NP. This means NP = coNP.



    The question of whether NP = coNP is open, but most theoretical computer scientists do not think it is very likely.




    So, assuming $NP ne coNP$, there exist problems that are decidable but neither in NP nor NP-hard. Note that we don't know that $NP = coNP$ implies $P = NP$. So this is a stronger assumption than the one you had suggested ($P ne NP$).






    share|cite|improve this answer














    I believe that this answer by Yuval Filmus all the questions you have asked.




    If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$neq$NP. If $A$ is a set and $f_i$ reduces SAT to $A$ in polytime, then $f_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f_i$ to get a polytime algorithm for SAT.



    We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.



    The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f_i$ is infinite). We define $A$ on $f_i(s)$ so that $s in SAT$ iff $f_i(s) notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s in A$ iff $|s| in K$.



    By construction, no polytime $f_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n in K$ (for $n geq 2$) by taking a majority of three strings of length $n$.




    To summarize,




    1. Halting problem is NP-hard.

    2. If $Pne NP$, not all undecidable problems are NP-hard.

    3. If $P = NP$, all non-trivial sets are NP-hard.


    The original answer had not addressed the last part of your question, namely, are there problems which are neither NP nor NP Hard? I will be lazy again and quote another answer, this time by Peter Shor.




    There is a problem which is both NP-hard and in coNP if and only if NP = coNP.



    If NP = coNP, than NP-complete problems (like 3-SAT) are both NP-hard and in coNP.



    On the other hand, if any NP-hard problem is in coNP, then all problems in NP are reducible to it, so all problems in NP are in coNP so NP ⊆ coNP. Now, since the complement of NP is coNP, and vice versa, we also have coNP ⊆ NP. This means NP = coNP.



    The question of whether NP = coNP is open, but most theoretical computer scientists do not think it is very likely.




    So, assuming $NP ne coNP$, there exist problems that are decidable but neither in NP nor NP-hard. Note that we don't know that $NP = coNP$ implies $P = NP$. So this is a stronger assumption than the one you had suggested ($P ne NP$).







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Dec 10 at 13:49

























    answered Dec 10 at 7:28









    Alex Smart

    1265




    1265








    • 1




      +1, I'd like to add that point 1 holds under the normal binary encoding of the halting problem; the unary encoding is not NP-hard, unless P=NP.
      – sdcvvc
      Dec 10 at 7:40










    • "not all undecidable problems are NP-hard" means that there are some undecidable problems are not in NP-hard, and that means P≠NP because if P=NP, all problems are NP-hard. So I think that we do not know whether "not all undecidable problems are NP-hard" before we solve P-NP problem. Am I correct?
      – Riddle Aaron
      Dec 10 at 7:55










    • @RiddleAaron That sounds right.
      – Alex Smart
      Dec 10 at 8:02














    • 1




      +1, I'd like to add that point 1 holds under the normal binary encoding of the halting problem; the unary encoding is not NP-hard, unless P=NP.
      – sdcvvc
      Dec 10 at 7:40










    • "not all undecidable problems are NP-hard" means that there are some undecidable problems are not in NP-hard, and that means P≠NP because if P=NP, all problems are NP-hard. So I think that we do not know whether "not all undecidable problems are NP-hard" before we solve P-NP problem. Am I correct?
      – Riddle Aaron
      Dec 10 at 7:55










    • @RiddleAaron That sounds right.
      – Alex Smart
      Dec 10 at 8:02








    1




    1




    +1, I'd like to add that point 1 holds under the normal binary encoding of the halting problem; the unary encoding is not NP-hard, unless P=NP.
    – sdcvvc
    Dec 10 at 7:40




    +1, I'd like to add that point 1 holds under the normal binary encoding of the halting problem; the unary encoding is not NP-hard, unless P=NP.
    – sdcvvc
    Dec 10 at 7:40












    "not all undecidable problems are NP-hard" means that there are some undecidable problems are not in NP-hard, and that means P≠NP because if P=NP, all problems are NP-hard. So I think that we do not know whether "not all undecidable problems are NP-hard" before we solve P-NP problem. Am I correct?
    – Riddle Aaron
    Dec 10 at 7:55




    "not all undecidable problems are NP-hard" means that there are some undecidable problems are not in NP-hard, and that means P≠NP because if P=NP, all problems are NP-hard. So I think that we do not know whether "not all undecidable problems are NP-hard" before we solve P-NP problem. Am I correct?
    – Riddle Aaron
    Dec 10 at 7:55












    @RiddleAaron That sounds right.
    – Alex Smart
    Dec 10 at 8:02




    @RiddleAaron That sounds right.
    – Alex Smart
    Dec 10 at 8:02










    up vote
    2
    down vote













    Your second diagram seems to be claiming that (assuming $mathrm{P}=mathrm{NP}$), every $mathrm{NP}$-hard problem that is not $mathrm{NP}$-complete is undecidable. That's certainly not true. For example, by the time hierarchy theorem, we know that $mathrm{NEXP}supsetneqmathrm{NP}$. $mathrm{NEXP}$ is a set of decidable problems and it contains $mathrm{NP}$-hard problems that are not in $mathrm{NP}$.






    share|cite|improve this answer

























      up vote
      2
      down vote













      Your second diagram seems to be claiming that (assuming $mathrm{P}=mathrm{NP}$), every $mathrm{NP}$-hard problem that is not $mathrm{NP}$-complete is undecidable. That's certainly not true. For example, by the time hierarchy theorem, we know that $mathrm{NEXP}supsetneqmathrm{NP}$. $mathrm{NEXP}$ is a set of decidable problems and it contains $mathrm{NP}$-hard problems that are not in $mathrm{NP}$.






      share|cite|improve this answer























        up vote
        2
        down vote










        up vote
        2
        down vote









        Your second diagram seems to be claiming that (assuming $mathrm{P}=mathrm{NP}$), every $mathrm{NP}$-hard problem that is not $mathrm{NP}$-complete is undecidable. That's certainly not true. For example, by the time hierarchy theorem, we know that $mathrm{NEXP}supsetneqmathrm{NP}$. $mathrm{NEXP}$ is a set of decidable problems and it contains $mathrm{NP}$-hard problems that are not in $mathrm{NP}$.






        share|cite|improve this answer












        Your second diagram seems to be claiming that (assuming $mathrm{P}=mathrm{NP}$), every $mathrm{NP}$-hard problem that is not $mathrm{NP}$-complete is undecidable. That's certainly not true. For example, by the time hierarchy theorem, we know that $mathrm{NEXP}supsetneqmathrm{NP}$. $mathrm{NEXP}$ is a set of decidable problems and it contains $mathrm{NP}$-hard problems that are not in $mathrm{NP}$.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Dec 10 at 10:30









        David Richerby

        65.5k1598187




        65.5k1598187






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Computer Science Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.





            Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


            Please pay close attention to the following guidance:


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f101316%2frelation-between-undecidable-problems-and-np-hard%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            數位音樂下載

            When can things happen in Etherscan, such as the picture below?

            格利澤436b