r/computerscience • u/Interesting-Status56 • Nov 28 '20
Scientists create the most efficient algorithm for the Traveling Salesman Problem (TSP) to date. Solving this problem would lead to many breakthroughs outside the field as computer science such as the ability to cure cancer.
39
u/SupahWalrus Nov 28 '20
Is it polynomial tho?
71
u/flumsi Nov 28 '20
If it was polynomial, it would be the biggest news in science this year.
21
0
Nov 29 '20
[deleted]
16
u/wernert12 Nov 29 '20
Since TSP is NP-Hard, this means all problems in NP can be reduced to TSP in polynomial time. If we are able to solve TSP in polynomial time, then all NP problems can be solved in polynomial time which shows P=NP.
10
52
Nov 28 '20
What's the actual bound improvement? I don't have time to wade through an entire podcast episode for a piece of info that may not be that impressive anyway.
1
u/cthulu0 Nov 30 '20
It is not impressive. They improved the bound by 1 - 10-36. So by 1.00000.......1
1
6
u/solinent Nov 28 '20 edited Nov 28 '20
My take from this: We're scientists now! hooray
The paper: https://arxiv.org/abs/2007.01409
It doesn't solve TSP but rather it solves it approximately. It's possible this could lead to a better provable bound for TSP like how A* works but it's doubtful. I think generally approximate TSP doesn't really have applications to theoretical or practical computer science, there are political and economical reasons that get in the way of the actual traveling sales/businessman, which causes certain people to favor certain routes and adds constraints to the problem which make it solvable by a mere human brain.
1
u/cthulu0 Nov 30 '20
Its even less impressive than that. There was already an approximate TSP algorithm. It improves on it by a factor of 1 - 10-36. In other words by a factor of 1.00000..........1
5
235
u/apajx Nov 28 '20
"Such as the ability to cure cancer"
Talk about sensational editorialization of a youtube title.