Strongly polynomial solvability of linear programming (Smale's Problem 9)

Linear programming with rational data is solvable in polynomial time in the bit model by the ellipsoid method and by interior-point methods, but every known algorithm's iteration count depends on the bit length of the input coefficients. Smale's Problem 9 — one of the longest-standing open questions in optimization, posed in Stephen Smale's 1998 list of problems for the twenty-first century — asks whether linear programming admits a strongly polynomial algorithm: one whose number of arithmetic operations and comparisons is bounded by a polynomial in the number of variables and constraints alone, while remaining polynomial in the bit model. The problem remains open as of August 2026. The frontier is precisely delimited: tropical-geometry lower bounds rule out strongly polynomial complexity for every self-concordant-barrier interior-point method and for short-step methods; exponential lower bounds are known for many simplex pivot rules; all known exact methods for general data are parameterized by condition or circuit-imbalance measures of the constraint matrix that can be exponential in the dimensions; and strongly polynomial algorithms are known only for special structures such as bounded subdeterminants, totally unimodular matrices, two-variables-per-inequality systems, binary systems, and Markov decision processes. The newest development (February 2026) proves that monotone circuit walks of strongly polynomial length always exist between vertices of a polyhedron, but no algorithm is known to find them.

Background

A linear program (LP) asks for the maximum of a linear objective over the polyhedron defined by finitely many linear inequalities, e.g. $\max\{c^{\top}x : Ax\le b,\ x\ge 0\}$ with rational data $A\in\mathbb{Q}^{m\times n}$, $b\in\mathbb{Q}^{m}$, $c\in\mathbb{Q}^{n}$. LP is among the most heavily used mathematical models in industry and science.

Two notions of polynomial time are distinguished for numerical input. An algorithm is weakly polynomial if its running time is bounded by a polynomial in the total bit length $L$ of the input encoding; it is strongly polynomial if (i) it is polynomial-time in the bit model and (ii) the number of arithmetic operations and comparisons it performs is bounded by a polynomial in the number of numerical entries of the input — here $m$ and $n$ — uniformly in the bit length of those entries. The ellipsoid method (1979), which iteratively shrinks an ellipsoid enclosing the solution set, and Karmarkar's interior-point method (1984), which traverses the interior of the feasible region, made LP weakly polynomial, but path-following interior-point methods need $O(\sqrt{n}\,L)$ iterations, and the simplex method — which walks between vertices of the feasible region — though fast in practice, exhibits exponentially many steps on known families of instances. Whether a strongly polynomial LP algorithm exists is Problem 9 in Stephen Smale's list of problems for the twenty-first century (1998), posed as finding a polynomial-time algorithm over the real numbers — in the model where arithmetic operations on input numbers count as single steps — for deciding feasibility of $Ax\le b$; the mainstream literature treats this as the strongly polynomial question for LP, feasibility and optimization being inter-reducible by standard strongly polynomial reductions.

Substantial partial results exist. Tardos (1986) gave a strongly polynomial algorithm whose complexity is bounded by a polynomial in $n$ and $\log\Delta_A$, where $\Delta_A$ is the largest absolute value of a square subdeterminant (the determinant of a square submatrix) of the constraint matrix — strongly polynomial whenever $\Delta_A$ is polynomially bounded, e.g. for totally unimodular matrices (matrices all of whose subdeterminants are $0$ or $\pm1$, the structure underlying network-flow and assignment LPs). Vavasis–Ye (1996) gave an interior-point method whose complexity depends only on a condition measure of the constraint matrix. Strongly polynomial algorithms are known for further special structures: linear systems having a binary solution (Chubanov 2012); Markov decision processes — the discrete stochastic control model solvable by LP — with a fixed discount rate (Ye 2011), and deterministic ones (Post–Ye 2015); totally unimodular LP (via Tardos; and Mizuno 2016, combining the simplex method with Tardos's auxiliary algorithm under a nondegeneracy assumption); and systems with at most two variables per inequality (Dadush–Kober–Koh 2026). None covers general rational data.

Three algorithmic routes have been delimited by lower bounds. (1) Interior-point methods (IPMs) drive a solution along the central path, the curve of minimizers of a barrier-augmented objective; a self-concordant barrier is the standard smoothness class of barrier functions underlying polynomial IPMs. Allamigeon–Benchimol–Gaubert–Joswig (2018) tropicalized the central path — replacing the real field by the max-plus semiring (arithmetic in which addition is replaced by maximization and multiplication by ordinary addition), under which the path degenerates to a piecewise-linear limit — and constructed LPs on which every log-barrier path-following IPM takes exponentially many iterations; Allamigeon–Gaubert–Vandame (2022) extended this to every self-concordant barrier, and Zong–Lee–Yue (2022) to short-step methods (conservative IPM variants that keep the iterate inside a narrow tube around the central path). The straight-line complexity (SLC) framework of Allamigeon–Dadush–Loho–Natura–Végh (2025) — SLC being the minimum number of segments of any piecewise-linear curve traversing a wide neighborhood of the central path — shows every path-following IPM needs at least SLC iterations, that SLC is at most $2^{n+o(1)}$, and that a subspace-layered IPM matches any such method up to $O(n^{1.5}\log n)$: IPMs are never much worse than the simplex method, but this framework provably cannot be strongly polynomial. (2) For the simplex method, whose iterations move between vertices of the feasible polyhedron along edges according to a pivot rule, Black (2024) proved exponential lower bounds for many concrete deterministic pivot rules. (3) The circuit-augmentation route generalizes simplex steps to circuits — directions given by support-minimal nonzero vectors in the null space of the constraint matrix, so one step may traverse several edges. The circuit diameter of a polyhedron is the maximum over vertex pairs of the minimum number of circuit steps between them; Natura (2026) proved it is $O(m^{2}\log m)$ for $\{x\in\mathbb{R}^{n} : Ax=b,\ x\ge 0\}$ with $A\in\mathbb{R}^{m\times n}$, a strongly polynomial bound resolving the circuit analogue of the question whether the combinatorial diameter (the analogous edge-walk quantity) is polynomially bounded. However, the existence of short circuit walks does not provide a rule that finds them without knowing the target vertex; and by a result of Black–Nöbel–Steiner (2026), approximating the shortest monotone circuit walk — one along which the objective value never worsens — within a factor $m^{1-\varepsilon}$ is NP-hard.

A complementary line parameterizes exact algorithms by the circuit imbalance measure $\kappa_A$ — the largest ratio between nonzero entries of a support-minimal null vector of $A$, a condition measure equal to $1$ for rescaled totally unimodular matrices and potentially exponential in the dimensions for rational data. Dadush–Huiberts–Natura–Végh (2020) gave a scaling-invariant IPM and Dadush–Natura–Végh (2020) an exact algorithm within Tardos's framework, both with complexity depending on the constraint matrix only through such measures; Cole–Hertrich–Tao–Végh (2023) achieved this for a first-order method (one using only gradient-type information per iteration); Dadush–Végh–Zambelli (2026) compute exact primal–dual solutions with $O(n^{2}\log(n/\delta))$ calls to a separation oracle — a subroutine that either certifies that a given point satisfies all the inequalities or returns a violated one — where $\delta$ is a geometric condition number of the system; and Dadush–Eisenbrand–Pinchasi–Rothvoss–Singer (2025) proved the structural bound $n\le O(d^{4}\kappa_A)$ for any real $d\times n$ matrix with non-collinear columns. For rational data all these parameters can still be exponential in $m$ and $n$, so every known exact method remains outside the strongly polynomial regime for general LP.

Problem Statement

Does there exist an algorithm that, given as input a linear program

$$\max\{\,c^{\top}x \;:\; Ax \le b\,\},\qquad A\in\mathbb{Q}^{m\times n},\ b\in\mathbb{Q}^{m},\ c\in\mathbb{Q}^{n},$$

always terminates with an exact description of the outcome — an optimal solution as an exact rational point, or the report that the system $Ax\le b$ is infeasible, or that the objective is unbounded on it — and satisfies both of the following:

1. the number of arithmetic operations and comparisons on rational numbers performed is bounded by a polynomial in $m$ and $n$ alone, independent of the bit length of the entries of $A$, $b$, $c$; and

2. the algorithm is polynomial-time in the bit model (equivalently, every intermediate rational number it manipulates has bit length bounded by a polynomial in the total input bit length)?

This is Smale's Problem 9 in its standard modern interpretation; the original 1998 formulation asks for a polynomial-time algorithm over the real numbers deciding feasibility of $Ax\le b$, and feasibility and optimization are inter-reducible by standard strongly polynomial reductions, so an algorithm satisfying properties 1 and 2 answers Smale's 1998 formulation affirmatively as well. This implication is one-directional: the original real-number-model requirement bounds only the number of arithmetic operations and does not by itself bound the bit length of the intermediate numbers, so it need not satisfy property 2, and a negative answer to the question above does not by itself settle Smale's formulation as posed. An affirmative answer consists of exhibiting such an algorithm together with a proof of correctness and of the two complexity properties; a negative answer consists of a proof, in a precisely defined model of computation that captures all algorithms satisfying properties 1 and 2, that no such algorithm exists.

References

1. Steve Smale, 'Mathematical problems for the next century', The Mathematical Intelligencer 20(2):7–15, 1998. DOI: 10.1007/bf03025291, https://doi.org/10.1007/bf03025291
2. N. K. Bakirov, 'Remark on the Smale's Problem 9', arXiv:1003.1008, 2010. https://arxiv.org/abs/1003.1008
3. N. Karmarkar, 'A new polynomial-time algorithm for linear programming', Combinatorica 4(4):373–395, 1984. DOI: 10.1007/bf02579150, https://doi.org/10.1007/bf02579150
4. Éva Tardos, 'A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs', Operations Research 34(2):250–256, 1986. DOI: 10.1287/opre.34.2.250, https://doi.org/10.1287/opre.34.2.250
5. Stephen A. Vavasis, Yinyu Ye, 'A primal-dual interior point method whose running time depends only on the constraint matrix', Mathematical Programming 74(1):79–120, 1996. DOI: 10.1007/bf02592148, https://doi.org/10.1007/bf02592148
6. Sergei Chubanov, 'A strongly polynomial algorithm for linear systems having a binary solution', Mathematical Programming 134(2):533–570, 2012. DOI: 10.1007/s10107-011-0445-3, https://doi.org/10.1007/s10107-011-0445-3
7. S. Mizuno, 'The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption', Optimization Methods and Software 31(6):1298–1304, 2016. DOI: 10.1080/10556788.2016.1208748, https://doi.org/10.1080/10556788.2016.1208748
8. Yaguang Yang, 'A double-pivot simplex algorithm and its upper bounds of the iteration numbers', Research in the Mathematical Sciences 7:34, 2020. DOI: 10.1007/s40687-020-00235-2, https://doi.org/10.1007/s40687-020-00235-2
9. Yinyu Ye, 'The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate', Mathematics of Operations Research 36(4):593–603, 2011. DOI: 10.1287/moor.1110.0516, https://doi.org/10.1287/moor.1110.0516
10. Ian Post, Yinyu Ye, 'The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes', Mathematics of Operations Research 40(4):859–868, 2015. DOI: 10.1287/moor.2014.0699, https://doi.org/10.1287/moor.2014.0699
11. Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig, 'Log-Barrier Interior Point Methods Are Not Strongly Polynomial', SIAM Journal on Applied Algebra and Geometry 2(1):140–178, 2018. DOI: 10.1137/17m1142132, https://doi.org/10.1137/17m1142132 (preprint arXiv:1708.01544, https://arxiv.org/abs/1708.01544)
12. Xavier Allamigeon, Stéphane Gaubert, Nicolas Vandame, 'No self-concordant barrier interior point method is strongly polynomial', Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), 2022. DOI: 10.1145/3519935.3519997, https://doi.org/10.1145/3519935.3519997 (preprint arXiv:2201.02186, https://arxiv.org/abs/2201.02186)
13. Manru Zong, Yin Tat Lee, Man-Chung Yue, 'Short-step Methods Are Not Strongly Polynomial-Time', arXiv:2201.02768, 2022. https://arxiv.org/abs/2201.02768
14. Xavier Allamigeon, Daniel Dadush, Georg Loho, Bento Natura, László A. Végh, 'Interior Point Methods Are Not Worse than Simplex', SIAM Journal on Computing 54(5), 2025. DOI: 10.1137/23m1554588, https://doi.org/10.1137/23m1554588 (preprint arXiv:2206.08810, https://arxiv.org/abs/2206.08810)
15. Daniel Dadush, Sophie Huiberts, Bento Natura, László A. Végh, 'A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix', Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020), 2020. DOI: 10.1145/3357713.3384326, https://doi.org/10.1145/3357713.3384326
16. Daniel Dadush, Bento Natura, László A. Végh, 'Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers', 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2020), 2020. DOI: 10.1109/FOCS46700.2020.00091, https://doi.org/10.1109/FOCS46700.2020.00091
17. Farbod Ekbatani, Bento Natura, László A. Végh, 'Circuit imbalance measures and linear programming', arXiv:2108.03616, 2021. https://arxiv.org/abs/2108.03616
18. Daniel Dadush, Zhuan Khye Koh, Bento Natura, László A. Végh, 'On Circuit Diameter Bounds via Circuit Imbalances', arXiv:2111.07913, 2021. https://arxiv.org/abs/2111.07913
19. Richard Cole, Christoph Hertrich, Yixin Tao, László A. Végh, 'A First Order Method for Linear Programming Parameterized by Circuit Imbalance', arXiv:2311.01959, 2023. https://arxiv.org/abs/2311.01959
20. Alexander E. Black, 'Exponential Lower Bounds for Many Pivot Rules for the Simplex Method', arXiv:2403.04886, 2024. https://arxiv.org/abs/2403.04886
21. Samuel Awoniyi, 'A strongly polynomial-time algorithm for the general linear programming problem', arXiv:2503.12041, 2025. https://arxiv.org/abs/2503.12041 (unverified resolution claim, not accepted by the community)
22. Daniel Dadush, Friedrich Eisenbrand, Rom Pinchasi, Thomas Rothvoss, Neta Singer, 'Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure', arXiv:2510.20301, 2025. https://arxiv.org/abs/2510.20301
23. Bento Natura, 'Circuit Diameter of Polyhedra is Strongly Polynomial', arXiv:2602.06958, 2026. https://arxiv.org/abs/2602.06958
24. Daniel Dadush, Stefan Kober, Zhuan Khye Koh, 'On Circuit Diameter and Straight Line Complexity', arXiv:2602.05699, 2026. https://arxiv.org/abs/2602.05699
25. Daniel Dadush, László A. Végh, Giacomo Zambelli, 'On finding exact solutions of linear programs in the oracle model', arXiv:2606.11820, 2026. https://arxiv.org/abs/2606.11820
26. Alexander E. Black, Christian Nöbel, Raphael Steiner, 'Short circuit walks in fixed dimension', Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), 563–573, 2026. DOI: 10.1137/1.9781611978971.23, https://doi.org/10.1137/1.9781611978971.23