are a list of eighteen unsolved problems in mathematics that was proposed by Steve Smale in 1998, and republished in 1999. Smale composed this list in reply to a request from Vladimir Arnold, then president of the International Mathematical Union, who asked several mathematicians to propose a list of problems for the 21st century. Arnold's inspiration came from the list of Hilbert's problems that had been published at the beginning of the 20th century.
Finding strongly polynomial algorithms for linear programming is one of the “mathematical problems for the 21st century"
according to Smale’s 9th problem: the linear programming problem
. Linear programming
, is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.
In the book, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation
by William J. Cook, it states linear programming is:"an amazingly effective method for combining a large number of simple rules, satisfied by all tours, to obtain a single rule of the form 'no tour through this point set can be shorter than X.' The number X gives an immediate quality measure: if we can also produce a tour of length X then we can be sure that it is optimal."
The simplex algorithm
, is a popular algorithm for linear programming. Mathematician George Dantzig provided an original example of this method by finding the best assignment of 70 people to 70 jobs to exemplify the usefulness of linear programming. The computing power required to test all the permutations to select the best assignment is vast; the number of possible configurations exceeds the number of particles in the universe. However, it takes only a moment to find the optimum solution by posing the problem as a linear program and applying the simplex algorithm.
Will it ever happen that somebody proves that the simplex algorithm, with a particular pivoting rule, runs in polynomial time? A polynomial pivot rule would solve this problem in the affirmative. Well, a necessary prerequisite for this to happen is that we can work from any vertex (corner) to another prescribed vertex in a small number of steps along the polyhedron or polytope. So whether or not there exists a polynomial-time variant of the simplex method depends on the geometry of polyhedra
(see the images).Hirsch conjecture
Warren Hirsch conjectured in 1957 that, for any polyhedron defined by n
inequalities (faces) in d
dimensions, the length of the longest shortest path between any two vertices is at most n - d
. When Francisco Santos announced his counterexample to the Hirsch conjecture in spring 2010, it sparked a flurry of activity examining the geometry and complexity of linear programming.
Santos gave three lectures, an 8 hour mini-course, on the Hirsch conjecture and the counter example. The three parts had the following entertaining titles:
• Hirsch Wars Episode I: The Phantom Conjecture
. This is mostly background and history, including the proofs of the two Klee-Walkup results on which his counter-example is based.
• Hirsch Wars Episode II: Attack of the Prismatoids
. The strong d-step Theorem and the construction of prismatoids in dimension 5 with large width.
• Hirsch Wars Episodes III and IV: Revenge of the Linear Bound + A New Hope
. The first part explores the asymptotics of counter-examples, and what we can (and cannot) expect from the prismatoid approach. The second part is about the diameter of simplicial complexes and more general objects, summing up some of the main results and ideas in the polymath3: The polynomial Hirsch Conjecture project.
For a more concise introduction see the talk Counter-examples to the Hirsch conjecture
); it is targeted at a general mathematical audience and focuses more on the context of the Hirsch conjecture (linear programming, simplex method, history) than on the counter-example itself. Santos concludes that this counter example breaks a “psychological barrier”
, but for applications it is absolutely irrelevant.Finding a counterexample will be merely a small ﬁrst step in the line of investigation related to the conjecture. (V. Klee and P. Kleinschmidt, 1987)