Travelling Salesman (2012 film)

Last updated
Travelling Salesman
TravellingSalesman MoviePoster.jpg
Directed byTimothy Lanzone
Screenplay byAndrew Lanzone
Timothy Lanzone
Produced byPreston Clay Reed
StarringMatt Lagan
Steve West
Danny Barclay
Marc Raymond
Tyler Seiple
David John Cole
Malek Houlihan
Eric Bloom
CinematographyBenji Bakshi
Edited byChristopher McGlynn
Music byBenjamin Krause [1]
Production
company
Fretboard Pictures [1]
Release date
  • June 16, 2012 (2012-06-16)
CountryUnited States
LanguageEnglish

Travelling Salesman is a 2012 intellectual thriller film about four mathematicians who solve the P versus NP problem, one of the most challenging mathematical problems in history. The title refers to the travelling salesman problem, an optimization problem that acts like a key to solving other difficult mathematical problems. It has been proven that a quick travelling salesman algorithm, if one exists, could be converted into quick algorithms for many other difficult tasks, such as factoring large numbers. Since many cryptographic schemes rely on the difficulty of factoring integers to protect their data, a quick solution would enable access to encrypted private data like personal correspondence, bank accounts and, possibly, government secrets.

Contents

The story was written and directed by Timothy Lanzone and premiered at the International House in Philadelphia on June 16, 2012. [2] After screenings in eight countries, spanning four continents, including screenings at the University of Pennsylvania and the University of Cambridge, [3] the film was released globally on September 10, 2013.

Plot

The four mathematicians are gathered and meet with a top official of the United States Department of Defense. After some discussion, the group agrees that they must be wary with whom to trust and control their solution. The official offers them a reward of $10 million in exchange for their portion of the algorithm, swaying them by attempting to address their concerns. Only one of the four speaks out against the sale, and in doing so is forced to reveal a dark truth about his portion of the solution. Before they sign a license to the government, however, they wrestle with the ethical consequences of their discovery.

Critical reception

The film premiered in Philadelphia, Pennsylvania on June 16, 2012, and early reviews were favorable:

"It is a great premise that writers Andy and Timothy Lanzone use to explore the theme of scientific hubris." [4]

"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." [4]

Mathematicians who have discussed the film praised the writer's attempt to bring a serious math problem to the big screen, although they questioned whether the world would be as dramatically affected by its solution:

"Despite our caveat that a solution to [the travelling salesman problem] might not be to die for, let alone to kill for, it would certainly be a huge change in our knowledge of the world. The implications could be unlimited. We certainly hope the movie raises awareness of computer science theory and the life importance of its subject matter." [1] [5]

The film also garnered favorable reviews after the University of Cambridge screening:

"And at the heart of this story was that mathematics now underpins so much of our lives, meaning that mathematical discoveries could have a dramatic impact on the world, leading to new advances or to potential catastrophe and all the moral dilemmas that entails. Perhaps an ethics class, or at least a trip to see this movie, might become an obligatory part of all maths degrees." [6]

Awards and recognition

2012 Silicon Valley Film Festival - Best Feature Film, Best Lead Actor (Danny Barclay), Best Editing (Christopher McGlynn) . [7]

2012 New York International Film Festival - Official Selection. [8]

See also

Related Research Articles

The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

<span class="mw-page-title-main">NP (complexity)</span> Complexity class used to classify decision problems

In computational complexity theory, NP is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.

<span class="mw-page-title-main">Travelling salesman problem</span> NP-hard problem in combinatorial optimization

The travelling salesman problem asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

<span class="mw-page-title-main">NP-hardness</span> Complexity class

In computational complexity theory, NP-hardness is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem.

<span class="mw-page-title-main">Greedy algorithm</span> Sequence of locally optimal choices

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

In graph theory, a branch of mathematics and computer science, Guan's route problem, the Chinese postman problem, postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (connected) undirected graph at least once. When the graph has an Eulerian circuit, that circuit is an optimal solution. Otherwise, the optimization problem is to find the smallest number of graph edges to duplicate so that the resulting multigraph does have an Eulerian circuit. It can be solved in polynomial time.

<span class="mw-page-title-main">Leonard Adleman</span> American computer scientist

Leonard Adleman is an American computer scientist. He is one of the creators of the RSA encryption algorithm, for which he received the 2002 Turing Award. He is also known for the creation of the field of DNA computing.

<span class="mw-page-title-main">Combinatorial optimization</span> Subfield of mathematical optimization

Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. A notable example of an approximation algorithm that provides both is the classic approximation algorithm of Lenstra, Shmoys and Tardos for scheduling on unrelated parallel machines.

<span class="mw-page-title-main">Cubic graph</span> Graph with all vertices of degree 3

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.

<i>k</i>-minimum spanning tree

The k-minimum spanning tree problem, studied in theoretical computer science, asks for a tree of minimum cost that has exactly k vertices and forms a subgraph of a larger graph. It is also called the k-MST or edge-weighted k-cardinality tree. Finding this tree is NP-hard, but it can be approximated to within a constant approximation ratio in polynomial time.

In mathematical optimization and computer science, heuristic is a technique designed for solving a problem more quickly when classic methods are too slow for finding an approximate solution, or when classic methods fail to find any exact solution. This is achieved by trading optimality, completeness, accuracy, or precision for speed. In a way, it can be considered a shortcut.

In computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: Lattice problems are an example of NP-hard problems which have been shown to be average-case hard, providing a test case for the security of cryptographic algorithms. In addition, some lattice problems which are worst-case hard can be used as a basis for extremely secure cryptographic schemes. The use of worst-case hardness in such schemes makes them among the very few schemes that are very likely secure even against quantum computers. For applications in such cryptosystems, lattices over vector space or free modules are generally considered.

<span class="mw-page-title-main">NP-completeness</span> Complexity class

In computational complexity theory, a problem is NP-complete when:

  1. It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no".
  2. When the answer is "yes", this can be demonstrated through the existence of a short solution.
  3. The correctness of each solution can be verified quickly and a brute-force search algorithm can find a solution by trying all possible solutions.
  4. The problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.

The Millennium Prize Problems are seven well-known complex mathematical problems selected by the Clay Mathematics Institute in 2000. The Clay Institute has pledged a US$1 million prize for the first correct solution to each problem.

In computational complexity theory, a gap reduction is a reduction to a particular type of decision problem, known as a c-gap problem. Such reductions provide information about the hardness of approximating solutions to optimization problems. In short, a gap problem refers to one wherein the objective is to distinguish between cases where the best solution is above one threshold from cases where the best solution is below another threshold, such that the two thresholds have a gap in between. Gap reductions can be used to demonstrate inapproximability results, as if a problem may be approximated to a better factor than the size of gap, then the approximation algorithm can be used to solve the corresponding gap problem.

<i>In Pursuit of the Traveling Salesman</i>

In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation is a book on the travelling salesman problem, by William J. Cook, published in 2011 by the Princeton University Press, with a paperback reprint in 2014. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.

References

  1. 1 2 3 Regan, K. W. "The Travelling Salesman's Power" . Retrieved April 26, 2012.
  2. ↑ "'Travelling Salesman' movie considers the repercussions if P equals NP". Wired UK. April 26, 2012. Retrieved April 26, 2012.
  3. ↑ "Travelling Salesman". Plus Magazine. March 14, 2013. Retrieved March 14, 2013.
  4. 1 2 Aron, Jacob. "'The moral uncertainty of a P = NP world".
  5. ↑ Pellien, Jessica (April 26, 2012). "Math goes to the Movies.. It's the year of the Travelling Salesman". Princeton University Press blog. Retrieved April 26, 2012.
  6. ↑ Thomas, Rachel (November 20, 2012). "Travelling Salesman". Plus Magazine. Retrieved November 20, 2012.
  7. ↑ "'List of Silicon Valley Awards 2012". Networked Blogs. November 13, 2012. Archived from the original on June 11, 2013. Retrieved November 13, 2012.{{cite web}}: CS1 maint: unfit URL (link)
  8. ↑ "'New York International Film Festival 2012 - Travelling Salesman". NYIFF. August 13, 2012. Retrieved August 13, 2012.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.