The linear feasibility problem takes a matrix and a vector and asks whether the system of linear inequalities in real unknowns
has a solution. By linear programming duality, optimizing a linear objective over such a set reduces to feasibility, so this decision problem carries the whole complexity of linear programming.
What "polynomial time" means here depends on the machine. In the bit model the input is a list of rational numbers, its size counts the bits of all numerators and denominators, and an algorithm is polynomial if it runs in time . In the real-number model the input is a list of exact real numbers, each arithmetic operation (), comparison, or memory move costs one unit, and a running time may only depend on and . An algorithm polynomial in this second sense is what Smale asks for; the closely related bit-model notion — arithmetic operations and polynomially bounded intermediate bit sizes — is called strongly polynomial. This mission fixes the real-number model precisely as a Blum–Shub–Smale (BSS) machine (Blum–Shub–Smale 1989): a finite program of instructions acting on a bi-infinite tape of real registers — loads of arbitrary real machine constants, exact field arithmetic at fixed addresses, two-sided tape shifts, a sign-test branch, and accept/reject — with cost equal to the number of executed instructions. The convention that costs something: the program must be uniform, one finite instruction list serving every , , and every real instance. Uniformity is exactly what separates the question from point-location tricks available to non-uniform families of decision trees.
For optimization, the question is the last gap in the complexity of its central problem. Linear programs with combinatorial structure already admit strongly polynomial algorithms — Tardos (1986) solved every LP whose running time may depend on the entries of but not on or , covering network flows and all -constraint problems — and a positive answer for general LP would extend that unification to the whole class, while explaining why simplex-type methods behave so well in practice (Spielman–Teng 2004).
For the theory of computation over the reals, the problem is a benchmark for what unit-cost exact arithmetic can do: it is Problem 9 on Smale's list of mathematical problems for the twenty-first century (Smale 1998), posed in the BSS model as the real-number analogue of the P-versus-NP style questions of that program, and it interacts with polyhedral combinatorics through the polynomial Hirsch conjecture: a polynomial bound on polytope diameters is a necessary condition for any polynomial pivot rule. A problem that calibrates both the practice of optimization and the foundations of real computation is a subject, not a special case.
The timeline splits into a negative branch (lower bounds against algorithm classes) and a positive branch (polynomial algorithms in weaker senses).
Lower bounds. Klee–Minty (1972) constructed a deformed cube on which Dantzig's largest-coefficient simplex rule visits all vertices; analogous exponential examples were later found for essentially every deterministic pivot rule, and randomized rules were driven to subexponential lower bounds by Friedmann–Hansen–Zwick (2011) — against upper bounds of from Kalai (1992) and Matoušek–Sharir–Welzl (1996). On the interior-point side, Allamigeon–Benchimol–Gaubert–Joswig (2018) showed by tropical methods that log-barrier path following is not strongly polynomial, and Allamigeon–Gaubert–Vandame (2022) extended this to every self-concordant barrier: no interior-point method of that class can settle the question positively.
Polynomial algorithms in weaker senses. Khachiyan (1979/80) proved LP feasibility is polynomial in the bit model via the ellipsoid method; Karmarkar (1984) and then Renegar (1988) brought interior-point methods to iterations. Megiddo (1984) solved LP in linear time for every fixed dimension; Tardos (1986) gave the combinatorial strongly polynomial class; Vavasis–Ye (1996) and Dadush–Huiberts–Natura–Végh (2020) replaced the bit size by condition measures of alone; Ye (2011) proved policy iteration strongly polynomial for fixed-discount Markov decision processes.
The central difficulty is visible in every positive result: each known iteration count is controlled by a scale-dependent quantity — bit length, condition number, barrier curvature — that is unbounded over the real instances with fixed. The naive plan, "run the ellipsoid method and round", fails at its first step in the real model: the number of iterations needed to separate a feasible system from an infeasible one grows with the thinness of the feasible set, which is not a function of ; no data-independent perturbation exists when the data are arbitrary reals. All results above are proved on paper only; none has a machine-checked proof in the literature. What is already formalized, on this platform, is the substrate this mission builds on: the simplex iteration (mission Introduction to Linear Optimization IV), the ellipsoid method with its volume-halving correctness theorem (XI), interior-point path following (XII), and self-concordance with the barrier method (Convex Optimization VI).
The mission's milestone list realizes this hierarchy in order; each level states what it deliberately leaves open.
Level 0 — the model works. A uniform BSS program decides one-variable feasibility in linear time:
It fixes nothing about ; its role is to certify that the machine model and cost semantics of the goal are non-vacuous.
Level 1 — the classical method is exponential. On the Klee–Minty cube, Dantzig's rule admits a run of
from the all-slack basis to the optimum. It leaves open all other pivot rules — extensions to further rules are welcome as strengthenings.
Level 2 — the bit model succeeds. Through the Cramer–Hadamard solution bound and the perturbation estimates, Khachiyan's theorem: for integer data bounded by , every admissible ellipsoid run decides feasibility within
The generous constants are deliberate — only the polynomial order is load-bearing. This level leaves open exactly the dependence on .
Level 3 — the goal (open). A uniform program with data-independent polynomial cost:
The statement asserts only the shape of the truth — no hard-coded degree or constant — so it is stable under every future quantitative improvement. These levels do not exhaust the project: Tardos' combinatorial LP theorem, Ye's fixed-discount MDP result, and impossibility statements for restricted program classes in the style of Allamigeon–Gaubert–Vandame are natural later milestones.
Polyhedra, simplex states, pivots, and ellipsoid runs are the platform's existing LinearOptimization development over Matrix (Fin m) (Fin n) ℝ, with as polyhedron A b; algorithms with data-dependent iteration counts are formalized as run predicates, as in the parent missions. The new SmaleNinth definitions supply what the goal genuinely needs and the run-predicate style cannot express: a concrete inductive type of BSS programs with operational semantics and unit-cost accounting, the Klee–Minty data with Dantzig's rule, and the explicit Khachiyan constants. One convention closes the degenerate escape hatch: the goal quantifies over finite BSSProgram terms under the fixed encodeLP input convention — formalizing "algorithm" as an arbitrary function would make the statement trivially true and is not the theorem. Division is totalized as and the branch test is ; both are benign for the class of programs quantified over.
The machine module is infrastructure beyond this mission — any real-number complexity statement (other Smale problems, sums-of-square-roots, BSS-completeness) can reuse it, as can any pivot-rule lower bound reuse the Klee–Minty module. Formalization forces distinctions the literature leaves informal: which machine variant carries the unit-cost claim, how ties in Dantzig's rule are resolved, and which of the interchangeable Khachiyan constants each estimate actually needs. Welcome contributions include proofs of any milestone, alternative exponential instances for other pivot rules, sharper constants in the Khachiyan module, and ports of the known strongly polynomial special cases.
theorem SmaleNinth.smale_ninth_problem :
∃ (P : BSSProgram) (C d : ℕ),
∀ (m n : ℕ) (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ),
∃ result : Bool,
BSSDecidesInTime P (encodeLP A b) (C * (m * n + m + 2) ^ d) result ∧
(result = true ↔ (polyhedron A b).Nonempty) := by sorryConsider the decision problem: given a matrix and a vector of arbitrary real numbers, decide whether the system of linear inequalities has a solution, that is, whether
where the inequality is componentwise. The instance is presented to a machine over the real numbers as tape cells (the two dimensions, the entries of in row-major order, then ), and the cost of a computation is the number of instructions it executes, each arithmetic operation, comparison and shift costing one unit regardless of the magnitude of the reals involved.
The assertion. There exist a single program , and constants , such that for every , every , every and every , the program started on the encoded instance halts with the correct verdict within
steps: it accepts if is nonempty, and rejects otherwise.
Reading the quantifiers. The program and both constants are chosen once, before any instance is seen; only the verdict and the actual halting time depend on the instance. The algorithm is therefore required to be uniform — one finite instruction list for all dimensions — and its running time to be bounded by a fixed polynomial in the number of input reals. In particular the bound may not depend on the magnitudes, the bit lengths, or any conditioning of and ; every algorithm currently known for this problem violates exactly this, its iteration count being governed by a quantity that is unbounded over real instances of fixed dimension.
What the statement deliberately leaves unfixed. Neither the degree , nor the constant , nor any structure of the program is prescribed: the claim is only that some polynomial bound holds, so it is invariant under future quantitative improvements and cannot be invalidated by a sharper analysis. Conversely, an algorithm is here a finite program in the fixed instruction set, not an arbitrary function of the input reals — a set-theoretic decision function always exists, and would make the statement vacuous.
This is Problem 9 on Smale's list of mathematical problems for the next century, and it is open.