3 ms·
a good reminder that the TSP optimization problem is only NP-hard, not NP-complete -- http://www.nomachetejuggling.com/2012/09/14/traveling-salesman-the-most-mi
by brockrockman 12y ago
a good reminder that the TSP optimization problem is only NP-hard, not NP-complete -- http://www.nomachetejuggling.com/2012/09/14/traveling-salesman-the-most-misunderstood-problem/ http://www.nomachetejuggling.com/2012/09/14/traveling-salesm...
- sidww2 12y ago"only" NP-hard? You know that NP-hard problems are equal to order harder than NP-complete ones, right?
- Strilanc 12y agoProbably referring to the definition, not the difficulty.
- codeflo 12y agoYes, 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).
- brockrockman 12y agodidn't mean to imply "only" as a less-than comparison -- just a distinction.