r/computerscience • • 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.

202 Upvotes

25 comments sorted by

235

u/apajx Nov 28 '20

"Such as the ability to cure cancer"

Talk about sensational editorialization of a youtube title.

41

u/Techfreak102 Nov 28 '20

To be fair, if they found a polynomial time algorithm to solve the TSP, then we would be able to solve cancer pretty quick. I want to say I learned in my masters Automata course that cancer gene sequencing/unraveling problems are in NPC, so if we had a P solution to TSP, we’d have a P solution to those cancer related problems. It wouldn’t be too far off as I understood it at the time

43

u/anon_95869123 Nov 28 '20

Unfortunately curing cancer will not be this simple.

One of the simplest issues with this ridiculously sensationalized title is the assumption that we gather a notable amount of data about cancer (EG: that doing DNAseq + RNAseq + Proteomics + etc. actually captures the majority of the biology of the disease). Tough to quantify, but I would argue we "quantify" <10% of the biology that occurs in cancer (and it is probably <1%).

TLDR: it doesn't matter how fancy an algorithm is if most of the relevant data isn't captured.

3

u/[deleted] Nov 29 '20

I've done plenty of real life wet -omics studies. At best, for me (YMMV), they were awesome hypothesis generating exercises. Generating answers, not so much.

-1

u/CreationBlues Nov 28 '20

Actually because the cell -omes (genomes, proteomes, etc) are dense networks with simple outputs and inputs, you don't need perfect knowledge of how they function. Otherwise modern medicine wouldn't work. The goal (dead cancer) is basic enough you don't need incredibly fine control over all the details.

What you're talking about is the level of precision and refinement needed for much more complicated tasks, like organism building. Things like building complicated 3d structures and so on. Of course, being able to solve NP problems means that science will look radically different.

9

u/anon_95869123 Nov 28 '20

the cell -omes (genomes, proteomes, etc) are dense networks with simple outputs and inputs, you don't need perfect knowledge of how they function.

The data is simple, the biology is not. To say that the quantity of peptide fragments that might have come from a particular protein determines what a cell is doing is to ignore a wealth of very well described function (post-transcriptional modification, affinity interactions, pH and oxidative state, etc.) and well described limitations of these technologies. Lets not even get into the fact that RNA quantity does not reliably represent protein function. Treating the -omes as you describe is one of many reasons we have 1000s of paper every year claiming that modulating a gene/protein/microRNA/insertyourfavoritemacrohere will improve cancer treatment and (almost) none actually work.

6

u/Petrosidius Nov 29 '20

Pretty sure the current barriers to cancer treatment are not computation.

3

u/adzawie Nov 28 '20

If the polynomial time algorithm is O(ngoogleplex ), then practically it’s still not computationally tractable...

-2

u/Techfreak102 Nov 28 '20

Well, that isn’t really realistic even if P=NP (which obviously it doesn’t). This is still an algorithm that someone is creating, so realistically you wouldn’t see anything beyond the possibility of an actual programmer. I’m pretty sure the worst problem I came across in my masters work that was borderline NP, but proven to actually be P, had something like a bound of O(n1000). So, ridiculous, but not that ridiculous when talking about super computers

1

u/tim466 Nov 29 '20

n1000 would be ridiculous plus there might be a huge constant.

4

u/18436572_V8 Nov 28 '20

I’m pretty sure Amazon will get us our stuff even faster, but curing cancer is a stretch

1

u/No_Sound_1179 Dec 26 '25

Happy cake day 5 years later :)

0

u/acroporaguardian Nov 29 '20

lol I know right

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

u/MissWatson Nov 28 '20

More like this millennium

0

u/[deleted] 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

u/[deleted] Nov 28 '20

[removed] — view removed comment

32

u/SupahWalrus Nov 28 '20

I’m not crying you are

52

u/[deleted] 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

u/[deleted] Nov 30 '20

Thanks for saving me the time!

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

u/new_reditor Nov 28 '20

Sounds like a ridiculous claim!