OP-0037OpenAlgorithms and data structures

A strongly polynomial algorithm for linear programming

Smale's ninth problem: is there an LP algorithm whose arithmetic operation count does not depend on the bit size of the input?

MSC 68W · Algorithms in computer science

Inferred from the community field; finer classification has not been reviewed.

0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

Is there an algorithm that decides feasibility of $\{x : Ax \le b\}$ , for rational $A \in \mathbb{Q}^{m\times n}$ and $b \in \mathbb{Q}^m$ , using a number of arithmetic operations bounded by a polynomial in $m$ and $n$ only — independent of the bit lengths of the entries?

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

Khachiyan's ellipsoid method and Karmarkar's interior-point method are polynomial in the bit-size model but not strongly polynomial. The question is the ninth of Smale's eighteen problems for the twenty-first century.

Known partial results

Tardos gave a strongly polynomial algorithm when the entries of $A$ are small integers, with running time depending on $A$ but not on $b$ or the objective.
Strongly polynomial algorithms exist for special structures: minimum-cost flow, and LPs with at most two variables per inequality.
Progress is entangled with the polynomial Hirsch conjecture, since a strongly polynomial pivot rule for the simplex method would need short paths on polytope graphs.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.