thxg

For context, the tests here are performed on 50- and 100-city instances, as they are limited by current GPU memory sizes. Meanwhile, the best heuristic code for TSP [1] frequently provides optimal solutions to 100k-city instances ("heuristic" = no optimality guarantee, like what this paper proposes; but one can then seek a proof of optimality if desired using a slower "exact" algorithm).

Also, Dantzig, Fulkerson and Johnson solved a 50-city TSP to optimality, with an exact method, by hand, in 1954 [2]. The practical running time was slower than what is proposed here, admittedly :-).

This is not a criticism of the paper, though: To their credit, the authors are quite straightforward about this, they're not trying to hide it. Their point is to demonstrate that their machine learning approach has potential.

[1] http://webhotel4.ruc.dk/~keld/research/LKH/

[2] http://www.math.uwaterloo.ca/tsp/uk/history.html

Oh, this needs a (2015). The bad wording was already highlighted here:

http://www.math.uwaterloo.ca/tsp/usa50/index.html

> To provide some context: If you started computing this problem on your home computer right now, you’d find the optimal route in about 9.64 x 1052 years — long after the Sun has entered its red giant phase and devoured the Earth

The above statement is only correct if you go for the naivest of brute force enumerations. As an alternative, you could use a mathematical programming code like Concorde [1], and solve the problem to optimality in under a second.

> If we’re willing to accept that we don’t need the absolute best route between all of the landmarks, then we can turn to smarter techniques such as genetic algorithms to find a solution that’s good enough for our purposes.

The particular TSP instance tackled heuristically in this post (i.e. without any optimality guarantees) is about the same size (50 cities) as that solved by Dantzig, Fulkerson and Johnson to optimality, by hand, in 1954 [2].

[1] http://www.math.uwaterloo.ca/tsp/concorde.html

[2] http://www.math.uwaterloo.ca/tsp/uk/history.html

> an empty dead section titled something like “who is talking about us” with no content

The design does not make it obvious but "they talk about us" is actually a clickable button, not a section heading.

"As many have noticed, our product line has been getting smaller and our tech support has been slowing down to a crawl. Unfortunately, the pandemic has been the final KO blow. It has hit our little town hard and we have not been able to recover from it. As of Tuesday, 11/24/20 17:00 EST ZaReason is no longer in business."

> Isn’t solving protein folding np-complete?

I'm not an expert on protein folding, but if you refer to this paper [1], it only claims that one particular optimization problem, believed to give a solution to protein folding problems, is NP-hard. So it is not proven that protein folding is hard (in terms of computational complexity theory), although it does seem likely.

> How did this new algo get past that?

This is a very frequent and legitimate question due to the widespread misconception that "large NP-hard problems cannot be solved". Maybe it does not help that the term "intractable" is often used as a synonym for "not in P", while that word has obvious connotations outside of complexity theory.

To the contrary, for some specific types of NP-hard problems, gigantic instances are routinely solved in a matter of minutes. Prominent examples are knapsack problems, SAT problems [2], and the Traveling Salesman Problem [3] or more generally Mixed Integer Programming [4]. To give you some intuition: yes, the complexity still grows exponentially with the size of the problem, but if the constant factor is really tiny, we may still be able to tackle fairly large instances.

> Did it solve p=np too?

Definitely not. For that, again, we would need, some formal statement that protein folding as solved there is NP-hard (this seems feasible, but I don't know that it has been done). Then, more importantly, we would need a theoretical result showing that the proposed solution method is of polynomial-time complexity -- being able to solve individual instances "quickly" is nice but not entirely relevant to the theoretical complexity side of things.

[1] "Complexity of protein folding", 1993, by Aviezri S. Fraenkel

[2] http://www.satcompetition.org

[3] http://www.math.uwaterloo.ca/tsp/

[4] http://plato.asu.edu/bench.html