Anti-Buzz: Traveling Salesman (Again)

by Andrew Emmott on September 13, 2014

in Anti-Buzz

Andrew has been writing Anti Buzz for 4 years resulting in almost 200 articles. For the next several weeks we will revisit some of these just in case you missed it.

So here’s something fun.

I’ve talked about the travelling salesman problem before. On one hand I should probably be happy that a serious Computer Science topic is given its own movie and sexed up for the general public, but I will be honest, this trailer makes me cringe.
This is anti-buzz after all, so let’s get to the task of dispelling the untruths and misdirections.
My first thought upon seeing this trailer was that it was going to unleash a new army of trisectors. What is a trisector? There is a famous old essay popular among mathematicians: What to do When the Trisector Comes? You do not have to be very math literate to appreciate it, and if you chose to just read that article instead of mine, I would not be offended.
In short, a trisector is a mathematical crank. A non-mathematician who for some reason gets it in their heads to either solve some daunting, open math question, or worse, one who attempts to ‘solve’ something mathematicians have already proven to be impossible. ‘Trisector’ is referring to someone trying to trisect an angle using only compass and straight edge, something the ancient Greeks proved impossible, and something that is largely irrelevant today because we have means of trisecting angles with better-than-ancient-Greek tools.

This trailer exaggerates the impact of finding an efficient solution to Traveling Salesman, but what upsets the crank-wary part of me is that it’s not entirely based in fiction; indeed a simple explanation of what’s really at stake does sound a bit like mathemagical sorcery: If an efficient solution to any NP-Hard problem, (Traveling Salesman is one such problem), is discovered, via reductions, this would in turn solve every other NP-Hard problem. Many NP-Hard problems are practical and have real-world implications; so the impact would be real.

The real scientific issue at stake is the question of P versus NP, two classes of problems that have different definitions but, maddeningly, nobody has proven are not equivalent. If they are not the same, then there are no efficient solutions for the NP-Hard problems, and if they are the same, then there are. While most scientists believe that P does not equal NP, the implications of them being the same are attractive to cranks: even now mathematicians are flooded with alleged proofs resolving the issue.

newface-620x461However, in the context of P versus NP, ‘efficient’ is a very loosely applied term. The layperson’s idea of computational efficiency is far more demanding than the bounds of poly-time algorithms. To put it in everyday terms, the difference between P and NP-Hard is the difference between years and centuries. Consumers want things done in less than a second. ‘Efficient’ solutions to Traveling Salesman would have a broad impact, but they would not lead to ‘everything can be done in a second’, but any other definition of efficiency means nothing to a consumer.

This misrepresentation of computational efficiency is a chronic problem; the average person has no concept of what really hard problems look like. The trailer suggests the film has no desire to rectify this, as the analogy used in the trailer once again misrepresents the issue. Finding a coin in the Sahara is not a complex problem. It is only time consuming because there is so much sand, but the solution is simple: look through all the sand. The ‘glass’ solution eliminates one dimension – an improvement – but we were already well within the bounds of efficiency, by our loose definition of efficiency. The really hard problems are not ones with lots of sand, but ones that are difficult even when you have very little sand to look through.

I’m also not sure why the trailer has the image of a drill entering somebody’s head. I don’t see how that becomes more efficient as a matter of P versus NP. We really don’t need to be giving the cranks more to be excited about. They already think what they are doing is magic.

Exaggerating the impact of traveling Salesman is forgivable: it’s a movie. Less forgivable is the anti-intellectual bent it has.

The trailer takes a turn for the uncanny with its use of the word ‘simplified’ presented not unlike some high-tech ad, preying on everyone’s fear that high-tech companies are luring us to our doom with their veneer of nice, simple, consumer-friendliness. People want to hate Google and its ilk for the influence and power they, even though they’ve pretty much only ever used it to make our lives better. People want to believe in stories that say they shouldn’t trust that.

I would rather we weren’t so cynical, but that is a tall order as long as computer science remains mysterious and magical to the average person.

by: at .


Comments on this entry are closed.

Previous post:

Next post: