Tag Archives: P versus NP problem

Private Screening of Travelling Salesman at GWU on 10/29

“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.”

You’re invited to a private screening of Travelling Salesman on October 29th at GWU!

The event is co-sponsored by the Washington DC Chapter of the Association for Computing Machinery (ACM), Data Community DC (DC2), the Washington DC Chapter of the Institute for Operations Research and the Management Sciences (WINFORMS), and the GWU EMSE Department and INCOSE Student Chapter.

Image

Where?  Funger Hall Room 103, George Washington University, 2201 G St NW, Washington, DC, 20052

When?  Tuesday, October 29, 2013. Doors open at 6.30PM, followed by the movie at 7PM.

Event Details:

This event is free, although donations ($5-$10) are welcome. Donations are not expected from students or faculty. To register, please RSVP using our Meetup group. Come anyways even if you do not RSVP.

Come join fellow OR, Analytics, and Computer Science practitioners for a free screening of Travelling Salesman, a 2012 intellectual thriller film about four mathematicians solving the P versus NP problem, one of the most challenging unsolved mathematical problems in history and one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a $1,000,000 prize for the first correct solution.

The title refers to the Travelling Salesman Problem (TSP), an optimization problem that acts like a key to solving other mathematical problems that are thought to be hard. By solving the TSP quickly the mathematicians can, for example, also factor large numbers quickly. Since many cryptographic schemes rely on the difficulty of factoring integers to protect their data this would allow access to private data like personal correspondence, bank accounts and possibly government secrets.

What is the Traveling salesman problem (TSP)?

The TSP 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 used as a benchmark for many optimization methods, and even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved.

What is the P versus NP problem, and how does it relate to the TSP?

The P versus NP problem is a major unsolved problem in computer science. Informally, it asks whether every problem whose solution can be ‘quickly verified’ by a computer can also be ‘quickly solved’ by a computer. It was introduced in 1971 by Stephen Cook in his seminal paper “The complexity of theorem proving procedures” and is considered by many to be the most important open problem in the field. The TSP is an example of such a problem that can be quickly verified, but it is unknown whether there exists a way for it to be ‘quickly solved’. As modern cryptography algorithms rely on the difficulty of solving large integer factorization problems, a proof of P=NP would have substantial implications for cryptographic systems

Why does the TSP matter?

The TSP has applications to planning, logistics, statistical inference problems and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing and vehicle routing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents traveling times or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources or time windows make the problem considerably harder.

Optimization algorithms are also useful for solving many statistical inference problems. For example, least absolute deviations regression attempts to minimize the sum of the absolute differences between data and a fitted trend line, whereas the more widely used ordinary least squares regression method attempts to minimize the sum of the squared deviations. While least absolute deviations regression is more robust to outliers than OLS, it does not have an analytical solving method (i.e., there is no closed-form equation that one can use to derive coefficient estimates) and therefore is solved via integer programming.