- #1

- 1,030

- 4

- Thread starter Dragonfall
- Start date

- #1

- 1,030

- 4

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

- 1

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

- Views
- 5K

- Last Post

- Replies
- 1

- Views
- 8K

- Last Post

- Replies
- 4

- Views
- 4K

- Last Post

- Replies
- 6

- Views
- 894

- Last Post

- Replies
- 4

- Views
- 614

- Last Post

- Replies
- 5

- Views
- 2K

- Replies
- 2

- Views
- 1K

- Replies
- 6

- Views
- 2K

- Replies
- 4

- Views
- 772

- Replies
- 1

- Views
- 2K