Math Conjectures

Strongly polynomial linear programming

OPENLandmarkOpen problemProposed 1983 · Full conjecture

Canonical statement

There is an algorithm which, for every rational A∈Qm×nA\in\mathbb Q^{m\times n}, b∈Qmb\in\mathbb Q^m, and c∈Qnc\in\mathbb Q^n, decides whether
max⁡{cTx:Ax≤b, x∈Rn} \max\{c^{\mathsf T}x:Ax\le b,\ x\in\mathbb R^n\}
is infeasible, unbounded, or has an optimum and, in the last case, returns an exact optimal solution, using at most p(m,n)p(m,n) elementary arithmetic operations and comparisons for one fixed polynomial pp, while every intermediate rational number has encoding length polynomial in the total input encoding length.
View source LaTeX
There is an algorithm which, for every rational \(A\in\mathbb Q^{m\times n}\), \(b\in\mathbb Q^m\), and \(c\in\mathbb Q^n\), decides whether
\[
\max\{c^{\mathsf T}x:Ax\le b,\ x\in\mathbb R^n\}
\]
is infeasible, unbounded, or has an optimum and, in the last case, returns an exact optimal solution, using at most \(p(m,n)\) elementary arithmetic operations and comparisons for one fixed polynomial \(p\), while every intermediate rational number has encoding length polynomial in the total input encoding length.
OPT-001:[Megiddo1983Genuinely][Smale1998Problems][DadushEtAl2024TwoNonzero]
Mathematical optimizationOperations researchTheoretical computer science

Notes

Smale's ninth problem asks whether linear programming admits a strongly polynomial algorithm: one using a number of arithmetic operations and comparisons bounded by a fixed polynomial in the dimensions mm and nn alone, independently of the magnitudes of the coefficients, while keeping every intermediate number of encoding length polynomial in the input length. The question was posed in this genuinely polynomial form by Megiddo in 1983 [Megiddo1983Genuinely] and given wide prominence by Smale in his list of mathematical problems for the next century [Smale1998Problems].

The known polynomial-time methods for linear programming, the ellipsoid and interior-point algorithms, run in time polynomial in the bit length of the input, so their operation counts grow with the coefficient sizes; they are not strongly polynomial. Strongly polynomial algorithms do exist for significant structured classes, most recently for linear programs with at most two nonzero entries per row or per column, due to Dadush, Koh, Natura, Olver, and Végh [DadushEtAl2024TwoNonzero].

For arbitrary constraint matrices the problem remains open: no strongly polynomial algorithm is known, and none has been ruled out.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.