多項式時間的精確旅行推銷員問題（TSP）解決方案？

Question

在多項式時間內是否有算法來準確解決（時間獨立的）TSP問題（沒有啓發式算法，節點不是空間中的點，成本是任意的）？

謝謝！

Answer 1

不，它被認爲是NP-Hard。

如果你找到一個，告訴我（當然在祕密的），我們會共同富裕:-)

我知道維基百科可以經常出錯，但你會發現在TSP有趣的頁面：

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

Answer 2

大概不會。它是NP-hard。

Answer 3

如果NP = P那麼答案是肯定的，可以用多項式時間完成。如果NP ≠ P，那麼答案是否定的，它不能在多項式時間內完成。 NP = P與NP ≠ P是一個懸而未決的問題，但我懷疑你會發現，那些對這個問題非常熟悉的代表性樣本將會有更多的人相信NP = P的人。

Answer 4

不！！，以多項式時間。
是的，有一個確切的算法。