Tag Archives: Computational complexity theory

Lunch & Learn: In pursuit of the salesman: Mathematics at the limits of computation with Bill Cook

TSPxkcd120.jpgThe traveling salesman problem, or TSP for short, is easy to state: given a number of cities along with the cost of travel between each pair of them, find the cheapest way to visit them all and return to your starting point. Simple to state, but remarkably difficult to solve! Despite decades of research by top applied mathematicians around the world, in general it is not known how to significantly improve upon simple brute-force checking. It is a real possibility that there may never exist an efficient method that is guaranteed to solve every instance of the problem. This is a deep mathematical question:

Is there an efficient solution method or not? The topic goes to the core of complexity theory concerning the limits of feasible computation. For the stout-hearted who would like to tackle the general version of the TSP, the Clay Mathematics Institute will hand over a $1,000,000 prize to anyone who can either produce an efficient general method or prove an impossibility result.

The complexity question that is the subject of the Clay Prize is the Holy Grail of traveling-salesman-problem research and we may be far from seeing its resolution. This is not to say that mathematicians have thus far come away empty-handed. Within the theoretical community the problem has led to a large number of results and conjectures that are both beautiful and deep. In the arena of exact computation, an 85,900-city challenge problem was solved in 2006, when the optimal tour was pulled out of a mind-boggling number of candidates in a computation that took the equivalent of 136 years on top-of-the-line computer workstations.

Continue reading

Lunch & Learn: Computational Intractability: A Barrier for Computers, Man, and Science with Sanjeev Arora

locksilverside.jpgWhile computers are exponentially more powerful and increasingly important in both society and in every area of scholastic inquiry, modern computers appear to be incapable of solving certain problems. In recent decades, computer scientists have begun to develop an understanding of what makes some computational tasks “intractable” not just for current computers but for all foreseeable computers, even if they were joined together.
Princeton is the lead institution for a new $10 million National Science Foundation grant for the study of computational intractability. At the Dec 10 Lunch ‘n Learn seminar, Sanjeev Arora, the principal investigator on the new grant, Professor of Computer Science, the Director of the Center for Theoretical Computer Science, and the Director of the Center for Intractability gave an overview of both the field and what the new center is trying to accomplish.

Continue reading