The moral uncertainty of a P = NP world

Jacob Aron, technology reporter

(Image: Travelling Salesman, 2012)

It is not often that espionage thrillers feature a round of peer review, but this early scene is a natural fit for Travelling Salesman, a film based on the premise that the biggest unsolved problem in computer science has been cracked.

When the film opens, Timothy Horton, a US-born mathematician currently at the University of Cambridge, and three colleagues are discussing whether or not to include an addendum on practical applications in a report of their latest theoretical research. You might think this is hardly a match for the explosive intros of James Bond films, but the mathematicians? work has the potential to do far more damage than 007?s entire career.

The problem in question is known as P vs NP and deals with the fundamental limits of computation. Briefly, P is the class of ?easy? problems than can be solved by an algorithm in a reasonable amount of time - multiplying two numbers together, for example. NP is the class of problems that are easy to check - if you are given an answer, you can quickly verify it - but otherwise difficult to solve.

The P vs NP problem, still unsolved after 40 years despite a $1 million bounty,? asks whether these two classes are actually identical. Most researchers believe they aren?t, as we seem to live in a world where some problems are simply fundamentally harder to compute than others.

Travelling Salesman takes place in the other world. Horton and colleagues have proved that P = NP, meaning they can easily solve a range of difficult real-world problems from gene sequencing to the eponymous travelling salesman problem, crucial for logistics and scheduling.

It also enables the mathematicians to crack any cryptography system in the world, which is why their four-year research project has been funded to the tune of millions of dollars by the US government. Now a smooth-talking spook has come to collect the proof and the ?non-deterministic processor? capable of swiftly cracking secret codes, but the mathematicians have begun to have mixed feelings about the implications of their work.

In the real world, some tricky mathematical caveats mean a proof that P = NP would not necessarily imply the ability to break cryptography, but it is a great premise that writers Andy and Timothy Lanzone use to explore the theme of scientific hubris. It is a well-worn trope in relation to genetic modification or to atomic bombs, and references to Los Alamos and Oppenheimer come thick-and-fast in Travelling Salesman, but one little discussed when it comes to maths.

Unfortunately, this means that the majority of the film consists of five men having a heated discussion in a stark, washed-out blue room in some anonymous government building. Other than Horton, we never even learn the characters? names. The low-budget aesthetic and grounding in hard science is reminiscent of the excellent time-travel film Primer, but Travelling Salesman is far less ambitious. A few flashbacks help break up the film, but you can?t help think this particular story would be better served as an hour-long play.

Travelling Salesman is still well worth watching though, especially for anyone with an interest in the consequences of mathematics rather than just its content. As Horton explains at a keynote conference speech, mathematicians have transformed our world, enabling mobile phones, GPS and Facebook, but also C4 explosives and enriched uranium. In A Mathematician?s Apology, G. H. Hardy sought to justify the pursuit of pure mathematics, stating that it seemed unlikely there would ever be a warlike application of number theory or special relativity, but cryptography and nuclear weapons proved him wrong. Travelling Salesman?s mathematicians are all too aware of what their work will do to the world, and watching them argue how to handle the consequences offers a thriller far more cerebral than most.

Travelling Salesman premieres on the 16th June at 4pm at International House Philadelphia, 3701 Chestnut Street, Philadelphia, PA 19104. After this the film will be shown on the international film festival circuit including the New York City International Film Festival in mid-August.

Follow @CultureLabNS on Twitter

Like us on Facebook

beverly hilton roland martin whitney houston dead at 48 whitney houston dead 2012 whitney houston passed away