Solving the NP-Completeness of Travelling Salesman Problem

  • Thread starter Thread starter Dragonfall
  • Start date Start date
Click For Summary
The Travelling Salesman Problem (TSP) is often misunderstood regarding its classification; it is NP-hard, but the decision version of TSP is NP-complete. Verifying if a given route is the shortest can be done in polynomial time, which is a key aspect of NP-completeness. The distinction lies in the fact that a problem is NP-hard if it can be used to solve an NP-complete problem in O(n) time. The discussion emphasizes the importance of understanding the decision version of TSP to grasp its complexity classification. Combinatorial optimization remains a compelling area of study due to these complexities.
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.
 

Thread 'Area of Overlapping Squares'

Here is a little puzzle from the book 100 Geometric Games by Pierre Berloquin. The side of a small square is one meter long and the side of a larger square one and a half meters long. One vertex of the large square is at the center of the small square. The side of the large square cuts two sides of the small square into one- third parts and two-thirds parts. What is the area where the squares overlap?
View full post »

Similar threads

Difficult to understand the solution provided in the video (travelling salesman problem)
  • · Replies 3 ·
Replies
3
Views
2K
P vs NP undecidable consequences
  • · Replies 1 ·
Replies
1
Views
1K
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
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
MHB NP-Complete Problems to Reading and Understanding
  • · Replies 4 ·
Replies
4
Views
2K
Practical effects if it is proved that P=NP
  • · Replies 9 ·
Replies
9
Views
3K
Will P Ever Equal NP as Technology Advances?
  • · Replies 5 ·
Replies
5
Views
3K
Is There a Polynomial Time Solution to the Travelling Salesman Problem?
  • · Replies 11 ·
Replies
11
Views
6K