Hacker News new | ask | show | jobs
by sidww2 4349 days ago
"only" NP-hard? You know that NP-hard problems are equal to order harder than NP-complete ones, right?
3 comments
Strilanc 4349 days ago
Probably referring to the definition, not the difficulty.
link
codeflo 4349 days ago
Yes, NP-complete is a subset of NP-hard. Grandparent states that NP-completeness only applies to decision problems (which is correct), but seems to think that NP-hardness applies to optimization problems (which is incorrect; NP-hard too is a class of decision problems).
link
brockrockman 4349 days ago
didn't mean to imply "only" as a less-than comparison -- just a distinction.
link