TSP for complete directeded graph

Question

完全な有向グラフでTraveling Salesman Problemの多項式時間アルゴリズムが存在しますか？

Answer 1

おそらくありません。ある場合は、グラフを取って、すべての欠けているエッジを非常に高い重みで追加することができます。そうすれば、問題の標準バージョンを解決することができます。これは、NP困難であることが知られています。