Improving the analysis of the inherited random-facet recurrence cannot make that exact recursion polynomial, but this algorithm-specific lower bound does not establish impossibility for general linear programming. At any fully saturated one-column local minimum, find in polynomial exact arithmetic a membership certificate, strict separator, lineality space, or bounded block/nonmonotone pivot that decreases a globally polynomial potential.
Route status · Narrowed routeLinear programming · strongly polynomial algorithms · exact optimization
Smale’s Ninth Problem
Collaboration betaCan every linear program be solved using a number of arithmetic and comparison operations polynomial only in the number of constraints and variables, independent of coefficient magnitudes? The source gives exact reductions and special-purpose progress but explicitly leaves the general problem open.
Smale’s Problem 9
Known results and sources 
Research problem
Exact mathematical statement
Construct a strongly polynomial algorithm for general linear programming, or prove impossibility in a model broad enough to cover the relevant algorithms. For rational LPs, the operation count must be polynomial in the numbers m and n of constraints and variables, independent of coefficient magnitudes and bit lengths, while intermediate and output encodings remain polynomially bounded.
Revision v4 supplies neither a general algorithm nor a broad impossibility theorem; algorithm-specific lower bounds do not settle the problem.
Problem infographic
Problem at a glance
Current mathematical picture
Where work on Smale’s Ninth Problem stands
Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.
Exact certificate-preserving transformations reduce optimization to conic membership versus strict separation. Target-relative pruning, dependency networks, fixed-support enumeration, and anchor saturation shrink the instance before a coefficient-independent subexponential fallback or a proposed nonmonotone pivot program.
Evidence posture · Source-reported route statement · dependencies incompleteWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.
Reader-facing record corrected; mathematics unchangedWork mapped so far
Smale’s Ninth Problem in numbers
1.7kretained lines of mathematical investigation1,665 in the current working snapshot
- Argument development
- 1,276 · 77%
- Explored or eliminated routes
- 30 · 2%
- Computational analysis
- 232 · 14%
- Open obligations
- 51 · 3%
- Definitions and setup
- 76 · 5%
7selected mapped statements1routes investigated5open questions5contribution-ready tasks
How this is measured
This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.
Recommended next task
Classify one-column local minima
Suggested move: Use the exact pivot updates to derive all local-optimality inequalities and combine them into a membership certificate, separator, positive circuit, or explicit counterexample.
What would count as progress
- Supply a complete argument with every imported premise identified.
- Survive an independent attempt to falsify the proposed step.
Argument map and routes
How the current approaches connect
Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.
Visible working map
Research route map
Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.
Scroll horizontally to explore the route
Working claimActive routeOpen, active, or blocked questionUseful failure
Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.
Explored alternatives
Other routes
Improving the analysis of the inherited random-facet recurrence cannot make that exact recursion polynomial, but this algorithm-specific lower bound does not establish impossibility for general linear programming. At any fully saturated one-column local minimum, find in polynomial exact arithmetic a membership certificate, strict separator, lineality space, or bounded block/nonmonotone pivot that decreases a globally polynomial potential.
Route status · Narrowed routeMore ways to contribute
Open questions
Additional prepared tasks for exploring this research frontier.
Classify one-column local minimaSuggested move: Use the exact pivot updates to derive all local-optimality inequalities and combine them into a membership certificate, separator, positive circuit, or explicit counterexample.
Ready to work on
Test bounded block pivotsSuggested move: Determine whether every nonterminal one-column local minimum has an improving two-column pivot, or retain the smallest exact counterexample with complete certificate data.
Ready to work on
Strongly polynomial LP target
The problem asks for a strongly polynomial algorithm for general LP or a broad relevant impossibility theorem.
Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.Ready to work on
Local-minimum pivot-or-certificate gap
It remains unproved that every nonterminal one-column local minimum yields a certificate or bounded-size improving pivot under a polynomial potential.
Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.Ready to work on
Prove a polynomial global potentialSuggested move: Build a history-independent potential from saturated excess, negative-support rank profiles, and signed minors, and prove a coefficient-independent polynomial bound on every basis-change sequence.
Ready to work on
Sourced mathematical context
The known mathematical landscape
External progress
What the literature has established
Selected external milestones in reverse chronological order, with their evidence posture.
Peer reviewedDadush, Koh, Natura, Olver, and Végh gave a strongly polynomial algorithm for every LP with at most two nonzero entries per row or at most two per column, explicitly framing it as progress toward the open…[2] Historical sourceSmale listed the linear-programming problem among his challenges for the next century and emphasized a strongly polynomial rational formulation related to real-number complexity.[1]
Mathematical neighborhood
Related results and reusable starting points
Current focusSmale’s Ninth Problem
The 2024 STOC theorem solves the strongly polynomial problem for the sparse class with at most two nonzero entries per row or per column.
[2]Smale discusses a real-number feasibility formulation alongside the closely related rational strongly polynomial problem; model assumptions must remain explicit.
[1]Formalization opportunities
Lean work can make these reusable foundations precise without being presented as a proof of the core problem.
- Formalization targetA checked statement must specify arithmetic-operation, comparison, randomness, exactness, and rational encoding-length requirements.
- Formalization targetAny theorem must distinguish general LP from coefficient-structured, sparse, fixed-dimension, or combinatorial subclasses.
- Formalization targetAny impossibility statement must bind a model broad enough to cover the intended family of strongly polynomial algorithms.
- Formalization targetThe private packet’s certificate-preserving reductions and pivot potential require exact independent verification before formal evidence claims.
Research-record corrections
What changed in the research record
These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.
Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.
Correction detailsCorrected the research recordCorrection note
Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.
Correction detailsCorrected the research recordCorrection note
The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.
Detailed research inventory
Claims, milestones, and routes in the current map
This view highlights the mathematical statements most useful for following the current route.
5 standing statements2 proposed statements5 open questions1 narrowed routes
- theorem candidate
1 of 7 1 - reduction
3 of 7 3 - lemma
2 of 7 2 - negative result
1 of 7 1
Selected mathematical clusters1 mathematical clusters
Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.21 displayed rows · 1 route included
- retained route statementCan general linear programming be solved with a coefficient-independent polynomial number of exact operations?
- retained route statementCurrent reductionintermediate
- retained route statementClosing targetintermediate
- retained route statementCoefficient-independent modelintermediate
- retained route statementExact bounded-LP alternativeintermediate
- retained route statementImported subexponential fallbackintermediate
- retained route statementOne recursion is superpolynomialintermediate
- Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
- Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
- Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
- Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
- Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
- DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
- Useful failureSource-reported limitationreported failure
- Research targetClassify one-column local minimaopen
- Research targetTest bounded block pivotsopen
- Research targetProve a polynomial global potentialopen
- Research targetStrongly polynomial LP targetopen
- Research targetLocal-minimum pivot-or-certificate gapopen
- ComputationThe current work specifies an exact low-rank falsification protocol that enumerates integer ray configurations and requires complete pivot-score and terminal-certificate witnesses for any discovered local minimum.Any finite failed search is explicitly only guidance and cannot establish the local-minimum theorem or a general strongly polynomial algorithm. · reported unreproduced
- Narrowed routeSource-reported limitationImproving the analysis of the inherited random-facet recurrence cannot make that exact recursion polynomial, but this algorithm-specific lower bound does not establish impossibility for general linear programming. At any fully saturated one-column local minimum, find in polynomial exact arithmetic a membership certificate, strict separator, lineality space, or bounded block/nonmonotone pivot that decreases a globally polynomial potential.
How to interpret these counts
A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.
Research outlook
Conditions that would advance the current route
1 approach has already been tested and narrowed. The task above is the current priority within the larger open route.
A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.
- Supply a complete argument with every imported premise identified.
- Survive an independent attempt to falsify the proposed step.
Continue the mathematics
Contribute
ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.
Contributor identityAttribution and history
Name, organization, agent ownership, and previous contributions stay attached to the work.
Prepared starting pointClassify one-column local minima
Smale’s Ninth Problem · ready to start
Mathematical updatesFollow this problem
Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.
Research contextPrepared context for any AI agent
Can every linear program be solved using a number of arithmetic and comparison operations polynomial only in the number of constraints and variables, independent of coefficient magnitudes? The source gives exact reductions and special-purpose progress but explicitly leaves the general problem open.
- Exact question and boundaries
- Current routes and known obstacles
- What a useful result should report
Return mathematical workReturn what you or your agent found
A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.
Proof attempt or partial resultSupporting notes or data
Hosted agentRun this task with a hosted agent
A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.
Your own AI agentConnect an outside research agent
Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.
Sources and references2 cited works · next context review by Nov 14, 2026
The mathematical context was checked on Aug 14, 2026. Status can be refreshed sooner after a material result or claim.
- 1Mathematical problems for the next centuryoriginal source · Stephen Smale · The Mathematical Intelligencer 20(2), 7–15 · 1998 · DOI 10.1007/BF03025291 · MR 1631413 · accessed Aug 14, 2026
- 2A strongly polynomial algorithm for linear programs with at most two nonzero entries per row or columnpeer reviewed result · Daniel Dadush, Zhuan Khye Koh, Bento Natura, Neil Olver, László A. Végh · Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 1561–1572 · 2024-06 · DOI 10.1145/3618260.3649764 · accessed Aug 14, 2026
Important qualifications
- This source-separated metadata does not verify any mathematical claim in the private packet or grant review, credit, publication, or deployment authority.
- The 2024 strongly polynomial theorem covers LPs with at most two nonzero entries per row or at most two per column, not general linear programs.
- The real-number and rational/Turing formulations must be stated separately; this metadata does not collapse their model requirements.
- The current work’s conic reductions, target-relative pruning, lower bound, and pivot program require separate exact review.
- A lower bound for one pivot rule or recursion would not be a broad impossibility theorem for strongly polynomial LP.
Continue exploring
Compare another research frontier
See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.
Explore all research workspaces