3 ms·
It's probably due to unfortunate naming of things. First, NP doesn't mean "non polynomial", though people can imply that since there are no known polynomial so
by dandanua 3y ago
It's probably due to unfortunate naming of things.
First, NP doesn't mean "non polynomial", though people can imply that since there are no known polynomial solvers for NP-complete problems. It's a shorthand for "nondeterministic polynomial", but that naming is not intuitive either. It's a class of problems that has polynomial verifiers of solutions.
Second, NP-hard means the problem is either NP-complete or not in NP at all. Which is another confusing naming, because problems not in NP are NP-hard.
As a saying goes, there are two main problems in programming - naming things and cache invalidation. And in this case the former fails badly.
- tgv 3y ago> Second, NP-hard means the problem is either NP-complete or not in NP at all. Which is another confusing naming, because problems not in NP are NP-hard. But remember that P is in NP, so NP-hard implies not in P (assuming P ≠ NP).
- deleted 3y ago[deleted]
- dandanua 3y agoAnd if P = NP any problem will be NP-hard. Until P ≠ NP is proved we can't heavily rely on the consequences.
- tgv 3y agoThat's an exaggeration. It's pretty safe to assume P ≠ NP, in practice. In theory you'd have to be more careful, but people have relied on weaker assumptions in math proofs. But for statements about super-mario, it's more than reasonable to assume.
- nine_k 3y agoSo, NP-hard means that it's either NP-complete (the hardest NP can get), or even harder than that. Pretty intuitive to me.
- WorldMaker 3y agoYeah, one way to always read it is that X-hard, for most Xs here, means at least as hard as X.
- justincredible 3y ago[dead]