The linked post mentions a previous post [1] where he mentions that proving you have the optimal path doesn't always require N! cost: > If you have an instance

The linked post mentions a previous post [1] where he mentions that proving you have the optimal path doesn't always require N! cost: > If you have an instance of the TSP of practical interest (i.e. it makes a difference to your life if you solve it or not, and it is really a TSP, not the result of some weird set of set of reductions from some other problem), then I bet you the Concorde program of Bill Cook and others will get you a provably optimal solution in a reasonable amount of time. In fact, I would be really interested in knowing the smallest “real” instance that Concorde cannot solve in, say, one day, on a normal laptop computer. Note the "provably" before "optimal solution". 1: http://mat.tepper.cmu.edu/blog/?p=6995 http://mat.tepper.cmu.edu/blog/?p=6995