Talk:Traveling Salesman Problem is NP-Complete

From ProofWiki
Jump to navigation Jump to search

Is the optimization problem really NP-Complete? It is easy to understand it's NP-Hard, but the given proof doesn't seem to hold for it to be NP. In plain: How do you check whether or not a given path is the shortest of all possible paths in the graph? You can easily calculate the lenght of this path, true, but checking if it is optimal would require solving the original optimization problem.

The short answer is yes, they are both NP-complete. The section with the title "The Function Version of the Problem is Reducible to the Decision Version of the Problem" is intended to show that the function problem is NP. The basic idea is that one can calculate the length of the shortest Hamilton cycle by using the decision problem to establish an upper and lower bound and then any Hamilton cycle with that length is a minimal cycle. Doing this does require solving about $ln(sn)$ instances of the decision problem to find the tight bound, and another $O(n^2)$ instances to find a path with that length, but in the end it is still just a polynomial increase to the length of the calculation. I am sorry if this was not clear on the page proper. Is there a way the article can be rewritten to make this more clear? --Emichael 11:06, 21 September 2011 (CDT)

According to this page [[1]] For now TSP-OPTIMIZE is in NP-Hard but not (necessarily) in NP, so its not in NP-Complete. TSP-DECIDE is both in NP-Hard as well as NP, and is therefore NP-Complete.Slacka (talk) 13:50, 10 November 2012 (UTC)

I can think of three explanations. The first is that there is some mistake on the wiki proof. I cannot find it so if someone with fresh eyes can take a look that would be helpful. The second option is that the definitions do not match up. For example the discrepancy may come from the definition of TSP in proofwiki that requires the weights to be integral. The third option is that the author of the linked page is incorrect.--Emichael (talk) 04:08, 12 November 2012 (UTC)
This proof is not ProofWiki compliant as it stands. There are too many statements that are reported as "we can show that", and part of the proof relies upon a link to a paper which is not held on this website. --prime mover (talk) 06:23, 12 November 2012 (UTC)


I haven't found a text book source yet, but several pages like this [2] claim, this proof is incorrect, as NP is a class of decision problems, so the solution has to be "yes" or "no". NP-complete problems are a subset of NP, so only decision problems can be NP-complete. TSP, the decision version is NP-complete. Since the optimization version is not a decision problem it can only be NP-hard, not NP-complete.Slacka (talk) 09:08, 4 January 2014 (UTC)

It would seem that what you are saying is that the assertion is meaningless. This is fundamentally different from the proof being incorrect. Lacking a source, the current definition on $\mathsf{Pr} \infty \mathsf{fWiki}$ does not stipulate that a problem has to be a decision problem in order to be NPC. In this sense, the current statement is not wrong, but I agree that it should be made more consistent with the conventions. I've added a "questionable" marker to reflect your points. — Lord_Farin (talk) 09:33, 4 January 2014 (UTC)
This is one reason why we are (or attempt to be) rigorous with links to all definitions used, and why, at one point, we made the decision to enforce a rule stating that all definitions are to be supported by a hard copy citation. This page is seriously non-compliant, in that a) no attempt was made to provide any links, and b) no hard-copy sources were entered.
As soon as someone with access to appropriate sources can fill in the details (i.e. write a page defining the concepts Definition:NP-Hard and Definition:NP-Complete then links to those pages can be used, and the precise statements may be made without confusion. If, as so often turns out, there exist more than one definition for either/both of these concepts, then we will attempt a synthesis of all such definitions and thence dispel any remaining confusion by, again, specifying precisely what is meant whenever such a term is used on $\mathsf{Pr} \infty \mathsf{fWiki}$.
Further to this, it appears the page Definition:NP-Complete has already been started -- using a different definition from the one expounded by Slacka. This needs to be resolved, and the sources from which the definition has been taken need to be specified. --prime mover (talk) 11:41, 4 January 2014 (UTC)
Also, links to blogs are not acceptable as sources for trivially obvious reasons, of course, except perhaps to contribute towards discussion on a talk page (such as this), so I have removed it from the page. --prime mover (talk) 11:38, 4 January 2014 (UTC)

The Euclidean TSP is NP-Complete per https://www.semanticscholar.org/paper/The-Euclidean-Traveling-Salesman-Problem-is-Papadimitriou/b151ce5e30980fdeda2fc2413250d6502cdddcc5. It does include a definition of what it means for the TSP to be Euclidean. Maybe the name of the page should be changed so that the assertion is true, e.g. to include the restriction to integer-valued co-ordinates and integer-valued Euclidean distances? Alternatively we rename to page to refer only to TSP-DECIDE, which is NP-Complete. Additionally we might want to consider adding a page for the Manhattan TSP being NP-Complete - that uses a similar construction used in the Euclidean case in the above paper and an alternative approach is used on p371 of "VLSI: Integrated Systems on Silicon: IFIP TC10 WG10.5 International". --John Coupe (talk) 19:00, 11 May 2020 (EDT)

Maybe we need another page to cover the result given at the link, because from the very name of it ("Euclidean") it appears to be a different result. --prime mover (talk) 01:53, 12 May 2020 (EDT)