Hacker News new | ask | show | jobs
by brockrockman 4358 days ago
a good reminder that the TSP optimization problem is only NP-hard, not NP-complete -- http://www.nomachetejuggling.com/2012/09/14/traveling-salesm...
1 comments
sidww2 4358 days ago
"only" NP-hard? You know that NP-hard problems are equal to order harder than NP-complete ones, right?
link
Strilanc 4358 days ago
Probably referring to the definition, not the difficulty.
link
codeflo 4357 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 4357 days ago
didn't mean to imply "only" as a less-than comparison -- just a distinction.
link