11
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ Linear Programming problems seem to get solved in polynomial time using the Simplex algorithm, it's just the proof that is missing. Plus the problem that there might be counter examples, but they seem very hard to find. $\endgroup$ – gnasher729 Dec 2 '16 at 13:48
  • 2
    $\begingroup$ @gnasher729 There are known counterexamples, e.g. the Klee-Minty cube. On the other hand, there are interior point algorithms known to run in (weakly) polynomial time. $\endgroup$ – Tavian Barnes Dec 2 '16 at 16:54
11
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.