- #1

- 1,030

- 4

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

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

Share: