Travelling Salesman Problem in sci-fi

I recently stumbled upon Toast, a collection of sci-fi short stories by 3 times Hugo Award Winner (the most prestigious awards in the genre) Charles Stross, now out of print and released under the Creative Commons License.

I was particularly fascined by Antibodies, for its premise: the Travelling Salesman Problem has been solved in polynomial time, therefore it is the end of the world.

The Travelling Salesman Problem, described in Wikipedia as "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?", is a problem pretty much ubiquitous in science, industry and also in everyday life (e.g. finding the most efficient path connecting pokèstops in your town while you are playing Pokèmon Go!).

How could a such seemingly harmless problem lead to the end of the world in "Antibodies"? Indirectly... more precisely since the TSP belongs* to the class of NP problems, and theoretically every NP problem can be reduced to another problem of the same class of complexity, a polynomial time (in the story an astonishing O(n2)) solution for the TSP implies that P=NP, and that every NP problem could be solved in polynomial time. Just to make an example cryptography is doomed in a such scenario.

Oddly, while P=NP would come with some really positive consequences for the mankind, in Antibodies we only see the bad ones. Dystopian futures sells more books, probably...

Maybe I am just splitting hairs, because this is a fictional work after all, but I could not help but note that in the story we are told that "someone's come up with a proof that NP-complete problems lie in P", but the TSP is not NP-complete but NP-hard, because given a solution you can't verify in polynomial time whether it is optimal or not. This mistake does not alter the "Antibodies" course of the story, in my opinion there is just a little inversion (solving the TSP in polynomial time would imply P=NP, but not the other way around).

Inaccuracies aside, I strongly recommend the story because it's short, intriguing, and one of those sci-fi improbable-but-not-too-much scenarios that makes you think.

Final note: I just can't end this post without this TSP's comic strip fromxkcd: looks like selling on eBay outperforms the doomsday algorithm.