3 ms·

> NP-hard is the set all problems at least as hard as NP-complete Im a bit confused by this. I thought NP-complete was the intersection of NP-hard and NP. Mayb

> NP-hard is the set all problems at least as hard as NP-complete Im a bit confused by this. I thought NP-complete was the intersection of NP-hard and NP. Maybe this is stating the same?

redleader55 1y ago
This [1] diagram from Wikipedia represents you are saying in a visual way. NP-hard and NP-complete are defined as basically an equivalence class modulo an algorithm in P which transforms from one problem to the other. In more human terms both NP-hard and NP-complete are reducible with a polynomial algorithm to another problem from their respective class, making them at least as hard. The difference between the two classes, again in human terms, is that NP-complete problems are decision problems "Does X have property Y?", while NP-hard problems can include more types - search problems, optimization, etc, making the class NP-hard strictly larger than NP-complete in set terms. The statement in the article means that NP-hard problems require solving a NP-complete problem plus a P problem - hence being at least as hard. [1] https://en.m.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg https://en.m.wikipedia.org/wiki/File:P_np_np-complete_np-har...
- zahlman 1y ago
  If NP-hard isn't even a subset of NP, why is it called "NP-hard"?
  - suzumer 1y ago
    Because a language being NP-hard implies it is at least as hard as the hardest NP problems. For any language that is NP-hard, if one had a turing machine that decided the language, one could construct a polynomial time transformation of any language in NP to the NP-hard language to decide it using the NP-hard turing machine.
  - sfink 1y ago
    Membership in NP is a statement about how easy a problem is (specifically, that you can verify an answer in no worse than polynomial time). NP-hard is about how hard a problem is (at a minimum). I wonder if there would be less confusion over this if NP had been called "NP-easy" in the first place. But Wikipedia says that by now that term has already been taken. P is "very easy": you can solve these in polynomial time. NP is "easy": you can verify a solution in polynomial time. Are there any problems you can verify but not solve in polynomial time? Nobody knows! (But ~everyone thinks so.) NP-hard is "hard": it takes polynomial time or more to even verify these.
  - Sharlin 1y ago
    Because naming things is one of the two difficult problems in computer science.
- edanm 1y ago
  I don't believe this is accurate. The difference between NP-Hard and NP-Complete is that NP-Complete problems are both NP-Hard, and in NP. As opposed to NP-Hard problems that are not NP-Complete, meaning they are not themselves in NP.
Khoth 1y ago
NP-complete is indeed the intersection of NP-hard and NP. If you can solve any NP-hard problem then you can solve any NP-complete problem (because you can convert any instance of an NP-complete problem to an NP-hard problem), so NP-hard problems are "at least as hard" as NP-complete problems. (But an NP-hard problem might not be in NP, ie given a purported solution to an NP-hard problem you might not be able to verify it in polynomial time)

> NP-hard is the set all problems at least as hard as NP-complete Im a bit confused by this. I thought NP-complete was the intersection of NP-hard and NP. Maybe this is stating the same?

redleader55 1y ago

This [1] diagram from Wikipedia represents you are saying in a visual way. NP-hard and NP-complete are defined as basically an equivalence class modulo an algorithm in P which transforms from one problem to the other. In more human terms both NP-hard and NP-complete are reducible with a polynomial algorithm to another problem from their respective class, making them at least as hard. The difference between the two classes, again in human terms, is that NP-complete problems are decision problems "Does X have property Y?", while NP-hard problems can include more types - search problems, optimization, etc, making the class NP-hard strictly larger than NP-complete in set terms. The statement in the article means that NP-hard problems require solving a NP-complete problem plus a P problem - hence being at least as hard. [1] https://en.m.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg https://en.m.wikipedia.org/wiki/File:P_np_np-complete_np-har...

zahlman 1y ago
If NP-hard isn't even a subset of NP, why is it called "NP-hard"?
- suzumer 1y ago
  Because a language being NP-hard implies it is at least as hard as the hardest NP problems. For any language that is NP-hard, if one had a turing machine that decided the language, one could construct a polynomial time transformation of any language in NP to the NP-hard language to decide it using the NP-hard turing machine.
- sfink 1y ago
  Membership in NP is a statement about how easy a problem is (specifically, that you can verify an answer in no worse than polynomial time). NP-hard is about how hard a problem is (at a minimum). I wonder if there would be less confusion over this if NP had been called "NP-easy" in the first place. But Wikipedia says that by now that term has already been taken. P is "very easy": you can solve these in polynomial time. NP is "easy": you can verify a solution in polynomial time. Are there any problems you can verify but not solve in polynomial time? Nobody knows! (But ~everyone thinks so.) NP-hard is "hard": it takes polynomial time or more to even verify these.
- Sharlin 1y ago
  Because naming things is one of the two difficult problems in computer science.
edanm 1y ago
I don't believe this is accurate. The difference between NP-Hard and NP-Complete is that NP-Complete problems are both NP-Hard, and in NP. As opposed to NP-Hard problems that are not NP-Complete, meaning they are not themselves in NP.

Khoth 1y ago

NP-complete is indeed the intersection of NP-hard and NP. If you can solve any NP-hard problem then you can solve any NP-complete problem (because you can convert any instance of an NP-complete problem to an NP-hard problem), so NP-hard problems are "at least as hard" as NP-complete problems. (But an NP-hard problem might not be in NP, ie given a purported solution to an NP-hard problem you might not be able to verify it in polynomial time)