Travelling Salesman

  • Thread starter Dragonfall
  • Start date
  • #1
1,030
4

Main Question or Discussion Point

I don't understand how travenlling salesman is NP-complete. In particular, how can you possibly verify that a given route is the shortest one in polynomial time?
 

Answers and Replies

  • #2
daniel_i_l
Gold Member
867
0
The TSP isn't NP-complete - it's NP-hard. But the question: Is there a path shorter than x is NP-complete. A problem is NP-hard iff it can be used to solve an NP-complete problem in O(n) time.
 
Last edited:
  • #3
329
0
TSP is only NP-complete if you use the decision version of the problem.

Side note, TSP is one reason why combinatorial optimization is one of my favorite subjects.
 
  • #4
1,030
4
This makes a lot more sense.
 

Related Threads for: Travelling Salesman

  • Last Post
Replies
1
Views
8K
  • Last Post
Replies
11
Views
5K
  • Last Post
Replies
4
Views
4K
Replies
3
Views
448
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
4
Views
456
Replies
2
Views
1K
Replies
6
Views
1K
Top