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

Is there an algorithm to solve the (time-indepenedent) TSP problem exactly (no heuristics, nodes are not points in space and cos开发者_运维知识库ts are arbitrary) in polynomial time?

Thanks!

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

Probably not. It is NP-hard.

If NP=P then the answer is yes, it can be done in polynomial time. If NP≠P, then the answer is no, it cannot be done in polynomial time. NP=P vs. NP≠P is an open problem, though I suspect you'll find that a representative sample of those sufficiently familiar with the issue will have more people who believe NP≠P than who believe NP=P.

No!, to polynomial time.
Yes!, to there is an exact algorithm.