Sorting the Travelling Salesman Problem

github.com

3 pointsenriquepablo3 comments

An attempt at understanding the difference that makes the sorting problem (the problem solved by sorting algorithms), but not the travelling salesman problem, efficiently solvable, looking at the topologies of their solution spaces.

Sorting has a simple local optimum implies global optimum property. If a list is sorted than any (not necessarily sequential) sublist is sorted, and the converse. No such property applies to TSP.

I think that the best way to think about why some combinatorial problems are hard and others easy isn't to ask what makes a problem hard, but rather what makes a problem easy. Combinatorial problems seem to be hard by default. It takes some special simplifying property to make them easy.

The idea here is not to understand why some combinatorial problems are hard and others easy, but rather to just be able to distinguish between them. So, instead of understanding why the measure functions structure the solution spaces the way they do, treating them as black boxes and examining the structure they provide to the solution space.

Reply on news.ycombinator.com