Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

What's the fundamental difference between the Knapsack problem and the travelling salesman (TSP) problem both of which are NP-hard, while the reality is that TSP could be solved much much faster?

share|improve this question

closed as unclear what you're asking by Noah S, Stefan Kohl, Steven Sam, Chris Godsil, Timothy Chow Jul 25 '14 at 2:18

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

It takes longer to pack for a trip than to take it? –  The Masked Avenger Jul 24 '14 at 17:02
haha, this really makes me laugh! –  user40780 Jul 24 '14 at 17:26
Studying why some theoretically hard problems seem to be practically easy is what gave rise to fields like parameterized complexity and average case complexity. I don't know what they have to say about these particular problems, though. –  Dan Turetsky Jul 24 '14 at 19:56
Could you cite what is the reality behind the claim "that TSP could be solved much much faster"? I don't doubt the claim; I would just be interested to learn of what's behind it. Thanks. –  Joseph O'Rourke Jul 24 '14 at 23:19
I agree with Joseph. To my knowledge, it is not the accepted view that the TSP can be solved "much much faster" than the knapsack problem. For example, theoretically, knapsack admits a FPTAS while (general) TSP is APX-complete (though Euclidean TSP admits a PTAS), so by that measure, knapsack is "easier." OTOH, if the question is about the solvability of "naturally occurring" instances, then user40780 needs to specify which classes of natural instances are being considered in each case. –  Timothy Chow Jul 25 '14 at 2:25