patternModerate
Does linear programming admit a strongly polynomial-time algorithm?
Viewed 0 times
linearpolynomialprogrammingstronglytimealgorithmdoesadmit
Problem
The linear programming problem: find a strongly-polynomial time algorithm which for given matrix A ∈ Rm×n and b ∈ Rm decides whether there exists x ∈ Rn with Ax ≥ b.
I know that Steve Smale's lists some of the unsolved problems in mathematics. But such a linear programming problem is it until now not-solvable ?
I know that Steve Smale's lists some of the unsolved problems in mathematics. But such a linear programming problem is it until now not-solvable ?
Solution
This problem is still open. See for example Wikipedia, which while not a dependable source in general, will probably be updated if a strongly polynomial time algorithm is ever found.
Context
StackExchange Computer Science Q#66796, answer score: 12
Revisions (0)
No revisions yet.