Sunday, 6 May 2012

Travelling Salesman - the Movie

Science in the movies is a topic we've looked at a few times here on the blog. But this one is for the pure mathematicians. Check out this preview to the upcoming flick "Travelling Salesman".



I love these kinds of films - overly melodramatic acting, a slight misrepresentation of the science behind the plot (which is OK by me as this is a movie), government conspiracies, and mysterious music. The name "Travelling Salesman" comes from the famous mathematical Travelling Salesman Problem in which a salesman needs to visit a numerous destinations and wishes to do it in the shortest time. Whilst this may seem to be a simple problem, it is one of the most studied problems in mathematics. The more destinations involved, the more difficult to solve and in general there is no algorithm that can find the best answer. Brute force methods (that is, computing every possible solution and then finding the best) are computationally difficult, and with too many destinations, impossible. Hence mathematicians often use heuristics which find good, although not necessarily optimal, solutions quickly.

The premise of the movie is that the famous P vs NP problem has been solved. I'm not a pure mathematician, so I'll do my best here... P problems are those whose solutions can be found quickly (in Polynomial time, hence the P). NP problems are those whose solutions can not be found quickly, but if somehow a solution is produced using some extra information, it is easy to check that this solution is the best one (in polynomial time). Solving these problems take Non-deterministic Polynomial time - hence NP. A good example to show this is a jigsaw puzzle - finding a solution may be very difficult (and it's probably most accurate to image a blind person doing the puzzle), but it only takes a quick glance to see if any solution is correct.

The question that mathematicians ask is whether P=NP - which means, are there algorithms out there that solve seemingly NP problems in polynomial time? We haven't found any yet and mathematicians tend to think that P does not equal NP, but there is currently no proof. Proving this one way or the other is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute and carries a US$ 1,000,000 prize for the first correct solution.

But why do we care? One of the reasons is that modern cryptography is based on the fact that P does not equal NP - this is the premise of the movie. Modern codes start with a pair of large prime numbers p1 and p2 and multiply them together to give  m=p1p2. The number m is released to the public, but p1 and p2 are kept secret. To crack the code you have to find p1 and p2, given the value of m. It turns out that finding the prime factors of large numbers (100+ digits) is exceptionally difficult, although checking an answer is very easy. It is thought to be an NP problem. But if indeed P does equal NP, this suggests that out there somewhere is an algorithm that could solve this problem in quick time, meaning that modern encryption codes are vulnerable.

They don't give too much away in the preview, but I suspect what happens is they prove P=NP, although the example of looking for something hidden in the desert seems like a P problem (you just check out under each grain of sand, which would be easy, although it's a nice illustration of the problem). We stretch the science here a bit - even if you prove P=NP, you still need to find the appropriate algorithm for the problem, which has never been done. But hey, it's a movie, and we don't pull Terminator up on its stretching of science!

There is a very good write up of the P vs NP problem over on Plus - check it out, it does a much more thorough job than I do!

15 comments:

  1. My favourite example of a problem in NP (in fact, it's NP-complete) is Sudoku. Enough people are familiar with Sudoku that you can get quite a lot across with that.

    (Of course, we're not just considering the order-3 Sudoku that we see in the newspapers, but a generalised order-n problem, but nonetheless, order-3 contains enough of the ideas to get them across to most people.)

    As with all problems in NP, checking that an answer to a Sudoku problem is correct is easy. Finding an answer is (believed to be) far more difficult.

    ReplyDelete
  2. You mention that even if you prove P=NP, you still need need to find the appropriate algorithm for the problem.  Actually, one of the most interesting properties of the class NP-complete, of which the traveling salesperson decision problem belongs, is that if you find an efficient polynomial time algorithm for any single problem in this class, you immediately get a solution for ALL problems in NP.  If a proof of P=NP exists, it presumably would come in the form of a polynomial time solution to some problem in NP-complete, meaning that you do not actually need to find a solution to your particular problem.  The proof immediately gives you a fast solution to ALL NP problems.  This is part of why showing P=NP would be crazy exciting.  Showing P not equal to NP would be amazing, but no nearly as much so.

    ReplyDelete
  3. The options for obtaining and viewing movies at home have certainly expanded in the past decade with the introduction of online movie rentalSerenity 2018 Watch Online

    ReplyDelete
  4. A lot of companies couple this feature with streaming programs. Often customers have access to a wider range of movies if they choose to sign up for a rental program that has both streaming and mail-order service.123movies

    ReplyDelete
  5. Diversion rentals are on the equivalent no time limit, no late charge program as the movies. couchtuner proxy

    ReplyDelete
  6. Now I tell everyone that asks how to make money online, to come to Associated Content.
    solarmovie website

    ReplyDelete
  7. We watch movies to relieve our stress and make the best use of our leisure time. The interesting movies can be great stress busters.solarmovie website

    ReplyDelete
  8. Sometimes, the webpage is overpowered by traffic and can be difficult to get to, which is a typical issue with free sites, so you may must be quiet.https://solarmovie.network/

    ReplyDelete
  9. You have done a great job.another website for free movies I will definitely dig it and personally recommend to my friends. I am confident they will be benefited from this site

    ReplyDelete
  10. Great article with excellent idea!Thank you for such a valuable article. I really appreciate for this great information.. Putlockers

    ReplyDelete
  11. It resembles betting with a bankroll that is free. When I give cash to the general population that set up shop outside of stores I don't anticipate anything back when I place cash in the case or container.
    TV & Movie Decals

    ReplyDelete
  12. very interesting post.this is my first time visit here.i found so mmany interesting stuff in your blog especially its discussion..thanks for the post!
    https://medium.com/@traveld/easyjet-flight-delay-compensation-2e85dd60a054/

    ReplyDelete
  13. Movies can some of the time have a decent or a dreadful story. There would be chances that you will lament viewing the movies you figured you would appreciate and how you wish that you can take your cash back.all movies for free online

    ReplyDelete