Strongly polynomial linear programming (Smale's 9th problem)

Unsolved Research level Archive

archive posted 8 weeks ago

Given a real $m \times n$ matrix $A$ and a vector $b \in R^{m}$ , decide whether there is $x \in R^{n}$ with $A x \geq b$ . Is there an algorithm whose number of arithmetic operations is bounded by a polynomial in $m$ and $n$ alone, independent of the size of the numbers in $A$ and $b$ ?

Posed by Stephen Smale, 1998

Like0

History and references

Still open as of 2026.

Linear programming was first shown to be solvable in polynomial time by Leonid Khachiyan's ellipsoid method in 1979, and Narendra Karmarkar's interior point method of 1984 made the approach practical. The running times of both depend on the number of bits needed to write down the input, not only on the number of variables and constraints. The simplex method is often fast in practice, but Klee and Minty built examples on which it takes exponentially many steps. Stephen Smale included the existence of a strongly polynomial algorithm as the ninth problem on his 1998 list of problems for the 21st century, and it is still open.

References

Solutions 0

Nobody has posted a solution here yet. Solutions written on Problempedia are credited to the people who write them.

References

Solutions 0

Discussion 0