In an ultimate battle of math versus the impossible, the impossible wins: it is likely no TSP solution method can have good performance on every data set as the number of points $n$ goes off to infinity. That said, the 1,000-year claim ignores over 70 years of intense mathematical study. A 22-city TSP can be handled in a snap with modern techniques, even on an iPhone. Going larger, examples with nearly 50,000 points and Google Map walking distances have been solved to precise optimality. And if we have a couple of million points to visit, say the nearest stars to our sun, then my money is on the math. Indeed, for this particular example, with 2,079,471 stars, we have a route that is guaranteed to be no more than 1.00002 times longer than a shortest possible solution. A few new ideas, perhaps from members of the audience, could nail down the optimal star tour.
Complexity theory suggests there are limits to the power of general-purpose
computational techniques, in science and elsewhere. But what are these limits
and how widely do they constrain our quest for knowledge? The TSP can play a crucial role in this context, demonstrating whether or not focused efforts on a single, possibly unsolvable, problem will produce results beyond our