Strongly polynomial linear programming
Can linear programs be solved by an algorithm whose number of arithmetic steps depends only on the number of variables and constraints?
Summary
Why it is open
A linear program asks for the maximum of a linear function subject to linear inequality constraints [6]. Stephen Smale made the question problem 9 of his 1998 list of "mathematical problems for the next century": "Is there a polynomial time algorithm over the real numbers which decides the feasibility of the linear system of inequalities Ax ≥ b?" [4]. He meant an algorithm for a machine that computes with real numbers, with time "measured by the number of arithmetic operations" [4]. A closely related question asks for a "strongly polynomial algorithm": one that works on rational inputs and is polynomial both in this arithmetic sense and in the usual sense of bit operations on a Turing machine [4]. Smale called problem 9 "the main unsolved problem of linear programming theory" [4]. The Wikipedia list of unsolved problems in computer science, which sets this page's status, asks whether linear programming admits a strongly polynomial algorithm [12].
Polynomial time as such is not the difficulty. Leonid Khachiyan and Narendra Karmarkar gave polynomial algorithms, but, as Éva Tardos wrote in 1986, "the number of arithmetic steps depends on the size of the input numbers" [2]. Francisco Santos notes that their algorithms are polynomial in the bit model of complexity but not in the real-number model [6]. The simplex method, which walks from vertex to vertex of the feasible region, is exponentially slow in the worst case, as Victor Klee and George Minty showed [4, 6].
A resolution would be a strongly polynomial algorithm, an algorithm in Smale's real-number sense, or a proof that none exists. No prize or committee sets the bar. One route has a known prerequisite: in Santos's words, "polynomial pivot rules cannot exist for the simplex method" unless the polynomial Hirsch conjecture on the diameters of polytopes holds [6].
What is known
Polynomial algorithms and the simplex method (1979–2004). Khachiyan's ellipsoid method was a polynomial-time algorithm for linear programming in the bit model, and Karmarkar's interior-point method was a practical algorithm that also runs in polynomial time in that model [4]. The simplex method is exponential in the worst case but, as Karl-Heinz Borgwardt and Smale showed, polynomial on average [4]. In 2004 Daniel Spielman and Shang-Hua Teng proved that its smoothed complexity, the worst expected running time when every input is slightly perturbed at random, is "polynomial in the input size and the standard deviation of Gaussian perturbations" [5].
Strongly polynomial special cases (1984–2024). Smale names partial results by Nimrod Megiddo and "especially" Tardos [4]. Megiddo showed in 1984 that a linear program with d variables and n constraints can be solved in O(n) time when d is fixed [1]. Tardos gave an algorithm whose number of arithmetic steps depends only on the size of the numbers in the constraint matrix, not on the right-hand side or the objective, which covers minimum-cost and multicommodity flows; whether an algorithm can also avoid the dependence on the constraint matrix "remains open", she wrote [2]. In the real-number model, Stephen Vavasis and Yinyu Ye gave an interior-point method that solves a linear program exactly in O(n^3.5 log(χ̄_A + n)) iterations, where χ̄_A is a condition measure of the constraint matrix A; in 2020 Daniel Dadush, Sophie Huiberts, Bento Natura and László Végh replaced χ̄_A by its smallest value over rescalings of the columns of A [8]. In 2024 Dadush, Zhuan Khye Koh, Natura, Neil Olver and Végh gave a strongly polynomial algorithm for every linear program with at most two non-zero entries per row, or per column, of the constraint matrix; any linear program, they note, reduces to one with at most three non-zero entries per column [10].
Diameters of polytopes (1957–2026). The largest diameter of the graph of vertices and edges among polyhedra of a given dimension and number of facets is a lower bound on the worst-case number of simplex iterations "with any pivot rule" [3]. Warren Hirsch conjectured in 1957 that a d-dimensional polytope with n facets has diameter at most n − d [6]. In 1992 Gil Kalai and Daniel Kleitman proved the quasi-polynomial bound n^(log d + 2) [3]. In 2012 Santos disproved Hirsch's conjecture with a 43-dimensional polytope that has 86 facets and diameter at least 44 [6]. A polynomial bound for all polytopes, the polynomial Hirsch conjecture, is still unproved: in a February 2026 preprint, not peer reviewed, Natura writes that "no polynomial bound is known for general polytopes" [11]. In the same preprint he proves an O(m² log m) bound on the circuit diameter of polyhedra {x : Ax = b, x ≥ 0} with m equality constraints [11]. The circuit diameter relaxes the diameter by allowing steps along every direction that an edge of a polyhedron with the same constraint matrix can have [11].
Limits of interior-point methods (2018–2022). Interior-point methods approximately follow the central path, a curve of solutions to penalised versions of the problem that converges to an optimum [9]. Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert and Michael Joswig proved in 2018 that primal-dual log-barrier interior-point methods are not strongly polynomial, using programs with 3r + 1 inequalities in dimension 2r on which the number of iterations is at least of order 2^r [7]. In 2022 Allamigeon, Gaubert and Nicolas Vandame extended the result to every interior-point method based on a self-concordant barrier, with an explicit program in dimension n with 2n constraints that, for large values of a parameter, needs at least 2^n − 1 iterations [9]. Dadush and colleagues summarise these papers as showing that, on such families, "no path-following method can be strongly polynomial" [10].
Main approaches
Simplex pivot rules. Find a rule for choosing the next vertex that needs only polynomially many steps, which would settle the question [6]. Strongest evidence: Santos quotes Michael Todd that the number of steps on a problem with m equality constraints "is almost always at most a small multiple of m, say 3m" [6]; the method is polynomial on average [4] and under small random perturbations [5], and diameters are at most quasi-polynomial [3]. Main difficulty: in 2012 Santos wrote that "exponential (or almost) worst-case behavior of the method is known for most of the pivot rules practically used or theoretically proposed" [6], and the route needs the polynomial Hirsch conjecture, still open in 2026 [6, 11].
Interior-point methods with combinatorial steps. Vavasis and Ye's layered least-squares steps let a method cross long, nearly straight stretches of the central path in a single iteration [10]. Strongest evidence: iteration bounds that depend only on the constraint matrix [8], and the 2024 algorithm for two non-zeros per row or column, built on a method whose iteration count is bounded by the straight-line complexity of the central path, the fewest pieces of a piecewise-linear curve that approximates it [10]. Main difficulty: the lower bounds for every self-concordant barrier method [7, 9], which apply to all path-following methods on those families [10].
Rounding and variable fixing. Solve an approximate version of the problem with rounded costs to deduce which variables sit at their bounds in an optimal solution, then fix them [10]. Strongest evidence: Tardos's algorithm for combinatorial linear programs, including flows [2]. Main difficulty: it runs in a number of iterations polynomial in n and in log Δ_A, where Δ_A is the largest subdeterminant of A, so it is strongly polynomial when all entries of A are at most polynomial in n [10]; for the class solved in 2024, even the rescaled condition measure may be unbounded [10].
Circuit walks. Move along circuit directions instead of edges [11]. Strongest evidence: the O(m² log m) circuit diameter, which Natura calls, to his knowledge, the first strongly polynomial bound on any diameter measure for general polyhedra [11]. Main difficulty: his walk is built between two given vertices, which does not yield an algorithm "since computing an optimal vertex is itself the problem we wish to solve"; he also cites an NP-hardness result for approximating the shortest monotone circuit walk [11]. The bound is in a preprint [11].
Open sub-questions
- Circuit augmentation. Is there a circuit-augmentation rule that reaches an optimal vertex, without knowing it in advance, in a number of steps polynomial in m, matching Natura's O(m² log m) circuit diameter [11]?
- Beyond path following. On the programs of Allamigeon, Gaubert and Vandame, where every self-concordant barrier method needs at least 2^n − 1 iterations, does some simplex pivot rule or other method take only polynomially many steps [9]?
- Three non-zeros per column. For which classes of linear programs with at most three non-zero entries per column is the straight-line complexity of the central path polynomial [10]?
- Diameters beyond unimodularity. Which classes of constraint matrices with unbounded subdeterminants have polytopes of polynomially bounded diameter, beyond the totally unimodular and bounded-subdeterminant cases [11]?
- The quasi-polynomial exponent. Can the exponent in the Kalai–Kleitman bound n^(log d + 2), since refined [11], be made o(log d), even only for d-polytopes with 2d facets, the hardest case by a lemma of Klee and Walkup [3, 6]?
Work on this in Papex
If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.
Key references
- Megiddo, N. (1984). Linear programming in linear time when the dimension is fixed. Journal of the ACM 31(1), 114–127. 10.1145/2422.322418 · Checked 15 Oct 2026
- Tardos, É. (1986). A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research 34(2), 250–256. 10.1287/opre.34.2.250 · Checked 15 Oct 2026
- Kalai, G. & Kleitman, D. J. (1992). A quasi-polynomial bound for the diameter of graphs of polyhedra. Bulletin of the American Mathematical Society 26(2), 315–316. 10.1090/S0273-0979-1992-00285-9 · Checked 15 Oct 2026
- Smale, S. (1998). Mathematical problems for the next century. The Mathematical Intelligencer 20(2), 7–15. 10.1007/BF03025291 · Checked 15 Oct 2026
- Spielman, D. A. & Teng, S.-H. (2004). Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. Journal of the ACM 51(3), 385–463. 10.1145/990308.990310 · Checked 15 Oct 2026
- Santos, F. (2012). A counterexample to the Hirsch conjecture. Annals of Mathematics 176(1), 383–412. 10.4007/annals.2012.176.1.7 · Checked 15 Oct 2026
- Allamigeon, X., Benchimol, P., Gaubert, S. & Joswig, M. (2018). Log-barrier interior point methods are not strongly polynomial. SIAM Journal on Applied Algebra and Geometry 2(1), 140–178. 10.1137/17M1142132 · Checked 15 Oct 2026
- Dadush, D., Huiberts, S., Natura, B. & Végh, L. A. (2020). A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020), ACM, 761–774. 10.1145/3357713.3384326 · Checked 15 Oct 2026
- Allamigeon, X., Gaubert, S. & Vandame, N. (2022). No self-concordant barrier interior point method is strongly polynomial. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), ACM, 515–528. 10.1145/3519935.3519997 · Checked 15 Oct 2026
- Dadush, D., Koh, Z. K., Natura, B., Olver, N. & Végh, L. A. (2024). A strongly polynomial algorithm for linear programs with at most two nonzero entries per row or column. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), ACM, 1561–1572. 10.1145/3618260.3649764 · Checked 15 Oct 2026
- Natura, B. (2026). Circuit diameter of polyhedra is strongly polynomial. Preprint, arXiv:2602.06958 (version 2, 10 February 2026), not peer reviewed. Source · Checked 15 Oct 2026
- Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 15 Oct 2026
Source
Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.