tag:blogger.com,1999:blog-3722233.post1193161077480806313..comments2022-12-02T17:41:58.702-06:00Comments on Computational Complexity: Is Traveling Salesman NP-Complete?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-22816705505680520382016-01-03T09:44:20.295-06:002016-01-03T09:44:20.295-06:00I did not talk about the Euclidian case, for the r...I did not talk about the Euclidian case, for the record.Anonymoushttps://www.blogger.com/profile/17790021012054552453noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57667969877008073332015-07-26T02:35:43.316-05:002015-07-26T02:35:43.316-05:00Hello all,
I find this old discussion very intere...Hello all,<br /><br />I find this old discussion very interesting but sometimes, i don't distinguish easily in your writings what is wrong and what is right. <br /><br />In fact, beyond the pure mathematical truth, people often need simple facts from all discussions.<br /><br />For example : yes TSP optimization problem is not NP-complete but if somebody find a polynomial algorithm for TSP optimization will be be sufficient to prove P=NP ?<br /><br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17310431409000292102014-01-10T16:03:18.423-06:002014-01-10T16:03:18.423-06:00Thanks to Marzio De Biasi who gave a nice reductio...Thanks to Marzio De Biasi who <a href="http://cstheory.stackexchange.com/questions/20538/co-np-completeness-of-minimal-tsp-tour/20546" rel="nofollow">gave a nice reduction</a> showing that a tour is shortest is indeed co-NP-complete. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3526345139852371722014-01-09T16:38:30.407-06:002014-01-09T16:38:30.407-06:00The biggest problem might be that some PROFESSORS ...The biggest problem might be that some PROFESSORS don't understand how to word TSP as an NP-complete problem. I'm not talking about the level of professors reading and writing here for the most part, but rather than at many of the thousands of colleges out there. Unlike those who teach that "NP" stands for "not polynomial" (a really bad error) there are some who were shown TSP as an optimization problem, were told it was NP-complete without being taught what NPC really means, and then teach their students (as a factoid) that TPC is NPC. Is that harmful?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28328813136266299462014-01-09T14:21:51.498-06:002014-01-09T14:21:51.498-06:00Ah, I see. The co-NP comment was about the "e...Ah, I see. The co-NP comment was about the "explicit edge weights" case, even though it is refering to a statement by Puget, who only talks about the Euclidean case. My mistake.Troels Bjerre Sørensenhttps://www.blogger.com/profile/05428948062041455645noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51113636449514211112014-01-09T14:21:19.203-06:002014-01-09T14:21:19.203-06:00"That problem is in co-NP..."
That stat..."That problem is in co-NP..."<br /><br />That statement wasn't about the Euclidean TSP, was it? :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47803954296897252442014-01-09T13:45:45.473-06:002014-01-09T13:45:45.473-06:00This comment has been removed by the author.Troels Bjerre Sørensenhttps://www.blogger.com/profile/05428948062041455645noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32922493488769613632014-01-09T11:59:36.515-06:002014-01-09T11:59:36.515-06:00The co-NP certificate is just a path of shorter le...The co-NP certificate is just a path of shorter length. All you have to do is verify it's a path and add up its weights. Certainly polynomial time.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66925560235897781912014-01-09T08:48:13.808-06:002014-01-09T08:48:13.808-06:00"Puget points out that even if we are given a..."Puget points out that even if we are given a tour, checking that it is the shortest tour is not believed to be in NP. That problem is in co-NP"<br /><br />Can you prove that it is in co-NP? Wouldn't that require deciding "Is this path shorter than that path?" in polynomial time? Isn't that just just SQRT-SUM in disguise, and therefore not known to be in P?Troels Bjerre Sørensenhttps://www.blogger.com/profile/05428948062041455645noreply@blogger.com