#### View:

 Message: [ First | Previous | Next | Last ] By Topic: [ First | Previous | Next | Last ] By Author: [ First | Previous | Next | Last ] Font: Proportional Font

Subject:

Re: RE> Floating Point Problem Solved EMERGENCY

From:

Robert I. Eachus

Date:

Thu, 13 Feb 1997 10:49:04 -0500

Content-Type:

text/plain

Parts/Attachments:

 text/plain (36 lines)
 ``` > 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 NP-complete.   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 with Standard_Disclaimer; use Standard_Disclaimer; function Message (Text: in Clever_Ideas) return Better_Ideas is... ```