HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Does linear programming admit a strongly polynomial-time algorithm?

Submitted by: @import:stackexchange-cs··
0
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 ?

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.