▲ | zahlman 5 days ago | |
If NP-hard isn't even a subset of NP, why is it called "NP-hard"? | ||
▲ | suzumer 5 days ago | parent | next [-] | |
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 5 days ago | parent | prev | next [-] | |
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 5 days ago | parent | prev [-] | |
Because naming things is one of the two difficult problems in computer science. |