- #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?

- Thread starter Dragonfall
- Start date

- #1

- 1,030

- 4

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?

- #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

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.

- Last Post

- Replies
- 1

- Views
- 8K

- Last Post

- Replies
- 11

- Views
- 5K

- Last Post

- Replies
- 4

- Views
- 4K

- Last Post

- Replies
- 3

- Views
- 448

- Last Post

- Replies
- 5

- Views
- 2K

- Last Post

- Replies
- 4

- Views
- 456

- Replies
- 2

- Views
- 1K

- Replies
- 6

- Views
- 1K