TEAM-ADA Archives

Team Ada: Ada Programming Language Advocacy


Options: Use Forum View

Use Proportional Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
"Mike F. Brenner" <[log in to unmask]>
Reply To:
Mike F. Brenner
Thu, 13 Feb 1997 05:48:52 -0500
text/plain (28 lines)
    > When (if) I get a paper published on an alternative algorithm to the
    > Traveling Salesman Problem, I'll be sure to drop a line here giving a
    > pointer to it. (As a teaser, I think I've found a way to find the solution
    > in N**2 rather than N! time, at least for points lying on the 2D Cartesian
    > plane.)

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.

If you actually think you have an Approximation, you should advertise
it as an Approximation.

If you actually think you have a Solution (not an Approximation),
and if you think it works on arbitrary subsets of the plane,
and if you think it is N**2 on large numbers of points,
and if you have tried it on large numbers of points,
   PLEASE LET ME SERVE AS YOUR REFEREE to give you a counterexample.
If you choose to publish it without a referee at least as knowledgeable
as I, please SUBMIT IT IN C NOT IN ADA, because a faulty solution would
detract from Ada advocacy. It will be refuted in minutes after the
experts find out it is posted.

Mike Brenner