Solving the NP-Completeness of Travelling Salesman Problem

  • Context: Graduate 
  • Thread starter Thread starter Dragonfall
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around the classification of the Travelling Salesman Problem (TSP) in terms of computational complexity, specifically addressing whether it is NP-complete or NP-hard. Participants explore the implications of different formulations of the problem, including the decision version and the verification of routes.

Discussion Character

  • Debate/contested, Technical explanation

Main Points Raised

  • One participant expresses confusion about how the TSP can be NP-complete, particularly questioning the polynomial-time verification of the shortest route.
  • Another participant asserts that TSP is NP-hard, clarifying that the decision version of the problem, which asks if there is a path shorter than a given length, is NP-complete.
  • A third participant notes that TSP is considered NP-complete only when referring to its decision version.
  • A side note mentions a personal interest in combinatorial optimization as a related topic.

Areas of Agreement / Disagreement

Participants exhibit disagreement regarding the classification of TSP, with some asserting it is NP-hard while others maintain it is NP-complete in the context of the decision version. The discussion remains unresolved as differing views are presented.

Contextual Notes

The discussion highlights the distinction between NP-completeness and NP-hardness, but does not resolve the implications of these classifications or the specifics of polynomial-time verification.

Dragonfall
Messages
1,023
Reaction score
5
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?
 
Mathematics news on Phys.org
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:
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.
 
This makes a lot more sense.
 

Similar threads

Graduate Difficult to understand the solution provided in the video (travelling salesman problem)
  • · Replies 3 ·
Replies
3
Views
3K
Graduate P vs NP undecidable consequences
  • · Replies 1 ·
Replies
1
Views
2K
Graduate A question about the Cook-Levin Theorem
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Real life traveling salesman problem
  • · Replies 6 ·
Replies
6
Views
2K
Undergrad NP vs P - difference between veryfing and answering
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Are electrons universal problem solvers?
  • · Replies 4 ·
Replies
4
Views
1K
Graduate Practical effects if it is proved that P=NP
  • · Replies 9 ·
Replies
9
Views
3K
Graduate Will P Ever Equal NP as Technology Advances?
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Is There a Polynomial Time Solution to the Travelling Salesman Problem?
  • · Replies 11 ·
Replies
11
Views
6K
If P = NP, can a proof be generated / verified efficiently for a proposition?
  • · Replies 52 ·
2
Replies
52
Views
4K