3 ms·
> 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 r
by 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.