I recently took a course offered by Professor Pascal Van Hentenryck @ Coursera called "Discrete Optimization." The course was about solving the NP Complete problems like 'Travelling Salesman', 'Graph Coloring', 'Vehicle Routing', 'Warehouse Locations' and so on. The course was very fascinating and at most challenging. The movie is based on the premises that NP problems, or Non- deterministic Polynomial time problems are not solvable in reasonable time. Even moderately sized such problems might take trillions of years with modern computing power. So, brute-force search is out of the question. For this reason, modern cryptography are based on this assumption. When mathematicians in the movie break this assumption and prove that P = NP, i.e. such problems can actually be solved in polynomial time, there are many implications. There is a moral dilemma that it might be used unethically and also such discoveries shouldn't be locked out and classified. As my professor put it, solving(optimizing) NP problems is the most important challenge that no one has heard about. I am really grateful to this movie for addressing this issue. But other than that, there isn't much for me in it. I was expecting a little more math and knowledge about their non-deterministic processor. But the movie is catered more towards the layman, which is perfectly understandable. Instead of just trivial and heuristic solutions, the movie could have mentioned few complete algorithms just to get some credibility amongst mathematics community. For those of you interested, there is a million dollar Millennium Prize offered by Clay Mathematics Institute for proving if P = NP or P != NP .
Review of Travelling Salesman
