Thu, 13 Feb 1997 10:49:04 -0500
> Congratulations on the awards you will win for proving that P=NP, since
> any solution to the Traveling Saleman Problem in polynomial time implies
> P=NP (and you have a quadratic solution!). On the other hand, you did
> not Say you had proven that P=NP, so maybe you meant you only have an
> approximation to a solution. There is a really big difference in this
> case between an approximation and a solution.
Technically the travelling salesman problem is NP-hard not
NP-complete. A variation on the TSP, asking to find a route of length
less than some k, however, is in NP. BUT, the subset of TSP in a
plane, with geometric distances, is not known or even thought to be
However, there is a substantial body of evidence that even with
distances which are greater than straight-line TSP (i.e. highway
distances) TSP is solvable in polynomial time. In the late fifties
there was a contest run by Gillette, I think, where the winner was to
be the person who submitted the shortest route through all 48 state
capitals. Good thing they put a tie breaker in the rules, thousands
of people submitted the best solution. I even remember reading a
paper on solving this particular problem by computer. Basically you
find a minimum spanning tree, which can be done quickly, then convert
the tree to a circut. The reason it is so easy can be summed up as "No
solution where edges cross can be optimal."
So N**2 would be really good for the geometric case, but not
earthshaking. Now if it works for TSPs with negative distances or
even in three dimensions, that would be exciting.
Robert I. Eachus
function Message (Text: in Clever_Ideas) return Better_Ideas is...