Timing Is Everything...

What if (against almost everyone's expectations) P actually equals NP???....

With fresh reports of the NSA cracking/hacking of internet encryption in the news, probably a good time for the award-winning, mathematical thriller* "Travelling Salesman" movie (about the P vs. NP problem) to be making its worldwide release... and... lo-and-behold it is!:

http://www.travellingsalesmanmovie.com/

reviewed a bit here:  http://plus.maths.org/content/travelling-salesman-0

and interview with the director here:  http://www.pulse-project.org/node/435


* yes Virginia, there is such a thing ;-)

The Traveling Salesman Problem Gets Real

(pic via Wikipedia)

Most folks are familiar with the Traveling Salesman Problem, one of the most famous dilemmas in all of math -- finding the shortest possible route between a given set of points (particularly ubiquitous in discussions of P vs. NP).
One real life example of TSP is route-scheduling for UPS delivery drivers who, every single workday, make on average, 120 deliveries. How most efficiently to drive that delivery route? There are a lot of consequences.

Apparently UPS has been field-testing a system, designated ORION ("On-Road Integrated Optimization and Navigation") which is their best algorithm for approximating a solution to TSP. So far they estimate it has saved them 35 million driving miles. Read more about it in the articles below (although they don't really give much information about the actual math behind ORION).

http://www.wired.com/business/2013/06/ups-astronomical-math/

http://www.fastcompany.com/3004319/brown-down-ups-drivers-vs-ups-algorithm

A quick couple of lines from the second piece:

“ 'Advanced analytics should be one of the top priorities for CIOs,' says Levis [UPS Director], who can talk of math in near-koans: 'Beyond knowledge is wisdom, and beyond that is clairvoyance.' Math simply can solve problems that humans can’t."

What If....

P = NP...!

I've reported previously on the independent film "Travelling Salesman" and now Plus.Maths.org has posted a (23-min.) podcast with the writer/director of the award-winning film here:

http://plus.maths.org/content/sites/plus.maths.org/files/podcast/pluspodcastnov2012.mp3

The thriller movie has to do with the consequences for a world in which the P vs. NP millennium problem is solved by proving that P = NP.

Wikipedia page on the film here:

http://en.wikipedia.org/wiki/Travelling_Salesman_%282012_film%29

A review of the movie here:

http://www.examiner.com/review/travelling-salesman-walking-the-tightrope-of-morality-math-science

A more technical take on the film from KW Regan here:

http://rjlipton.wordpress.com/2012/04/22/the-travelling-salesmans-power/

And finally, homepage for the film here:

http://www.travellingsalesmanmovie.com/

Unfortunately, though the film has been out for awhile now on the festival circuit, I can't find any info as to actual schedule dates where it is playing, nor if it would perhaps ever get wider distribution? (if anyone knows where to look for a schedule of play dates please let us know).

P vs. NP... on the Big Screen?

Assuming you're familiar with the "travelling salesman" problem and related P vs. NP debate, then this trailer for a forthcoming (mid-June) movie may be of interest?? -- I thought it was some sort of parody when I first viewed it, but I guess it's a for real thriller! (from "Fretboard Pictures" ??? -- no idea how wide a distribution it will have -- if anyone can fill in more details, would be curious to learn more):



(h/t to @AndrewEckford)

Connecting the Dots (or Cities)...

Via Wikimedia Commons

Sol Lederman, over at 'Wild About Math' is already up with his 2nd podcast interview, this time with William Cook, author of "In Pursuit of the Traveling Salesman." If this famous and fascinating math conundrum interests you, definitely tune in (…ohh, and p.s., it ought interest you! ;-) -- it is one of the Clay Institute's million-dollar problems):

http://wildaboutmath.com/2012/02/17/william-cook-inspired-by-math-2/

And here's a short review of Cook's book from elsewhere on the Web:

http://www.mathteacherctk.com/blog/2011/12/in-pursuit-of-the-traveling-salesman/

The Traveling Salesman Problem... and Art

Alex Bellos addresses the Travelling Salesman Problem and William Cook's new book on the subject, and also artwork, here:

http://alexbellos.com/?p=1629

Collaboration via NY Times

The NY Times "Numberplay" column this week addresses "open science," collaboration, and the Traveling Salesman Problem:

http://wordplay.blogs.nytimes.com/2012/01/16/open-science-numberplay-style/

The column poses two problems (one involving numbers/distances and one involving words/letters) for readers to work on. I'll be interested to see how well collaboration succeeds, in particular, on the first, enormous  problem.

(The inspiration for this column, by the way, was the following, more general Times piece on collaborative science in the digital age: http://tinyurl.com/78apwyy )

Travelling Salesmen and Travelling Bees

The "travelling salesman problem" is a classic mathematical conundrum (about how to optimize a salesman's travel route when visiting several different cities), that mathematicians hunt for an algorithmic solution to.
Perhaps they should consult with bees:

http://www.sciencedaily.com/releases/2011/06/110628191339.htm

"Computers solve it by comparing the length of all possible routes and choosing the shortest. However, bees solve simple versions of it without computer assistance using a brain the size of grass seed."