Exact Traveling Salesman Problem (TSP) solution in polynomial time?

Question

Is there an algorithm to solve the (time-indepenedent) TSP problem exactly (no heuristics, nodes are not points in space and costs are arbitrary) in polynomial time?

Thanks!

Answer 1

No. It is considered NP-Hard.

If you do find one, tell me (in secret of course) and we'll be rich together :-)

I know Wikipedia can be often wrong, but you might find their page on TSP interesting:

http://en.wikipedia.org/wiki/Travelling_salesman_problem