13
$\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 ?

Improve this question
$\endgroup$
3
  • $\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
    Commented Dec 2, 2016 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
    Commented Dec 2, 2016 at 16:54
  • $\begingroup$ This paper is related: cc.gatech.edu/~vempala/papers/affine.pdf $\endgroup$
    – Erel Segal-Halevi
    Commented Jul 19, 2019 at 4:29

2 Answers 2

Reset to default
12
$\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.

Improve this answer
$\endgroup$
-2
$\begingroup$

The algorithm used to solve this problem is the simplex algorithm. This is an efficient algorithm which can solve linear programs in polynomial time. The algorithm starts with an initial feasible solution to the problem and then iteratively improves it until a maximum or minimum is found. This can be done by using the following steps:

  1. Construct the initial feasible solution (the initial basic solution) by solving the inequality Ax ≥ b.

  2. Choose a direction vector that will increase or decrease the objective function value.

  3. Calculate the new basic solution by improving the current basic solution along the chosen direction vector.

  4. Repeat steps 2 and 3 until an optimal solution is found.

The complexity of the simplex algorithm is O(mn2) in time and O(mn) in space, where m and n are the dimensions of the matrix A. Therefore, it can be seen that the simplex algorithm provides an efficient, strongly-polynomial time solution to the linear programming problem.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Are you generating answers with ChatGPT? That is unlikely to be welcome or appropriate here (see, e.g., stackoverflow.com/help/gpt-policy). In particular, if you do use ChatGPT, you must provide attribution for the source: meta.stackexchange.com/a/384648/160917. This answer fails to provide attribution, which violates our rules regarding referencing your sources: cs.stackexchange.com/help/referencing. If a user flags this answer in its current form, it is likely to be deleted. $\endgroup$
    – D.W. ♦
    Commented Jan 24, 2023 at 5:00
  • $\begingroup$ This answer contains claims that are wrong. No, the simplex method is not known to run in strongly polynomial time. No, its running time is not $O(mn^2)$. The worst-case running time of the simplex algorithm is exponential -- and, in any case, not polynomial. See, e.g., en.wikipedia.org/wiki/…. Moreover, the size of intermediate values computed during the algorithm might grow to exponential size; strongly polynomial time requires that they remain of polynomially bounded size. $\endgroup$
    – D.W. ♦
    Commented Jan 24, 2023 at 5:03
  • $\begingroup$ ChatGPT has been called Dunning-Kruger on steroids. Yes, this looks like it. Or maybe it’s not artificial intelligence but natural stupidity. Downvoted because utterly wrong. $\endgroup$
    – gnasher729
    Commented Jan 24, 2023 at 7:11
  • $\begingroup$ First, consider the case when the matrix A is of full rank. In this case, the simplex algorithm will converge to the optimal solution in at most O(mn2) iterations. Each iteration takes O(mn) time, resulting in an overall time complexity of O(mn2). Second, consider the case when the matrix A has linearly dependent columns. In this case, the simplex algorithm can be used to identify a feasible solution in O(mn) time as it can determine if an inequality is satisfied in O(mn) time. This shows that the simplex algorithm can solve the linear programming problem in strongly polynomial time. $\endgroup$
    – archimede
    Commented Jan 24, 2023 at 12:43
  • $\begingroup$ That's not correct. There is no such guarantee on the number of iterations. Where are you getting that from? What is your justification or source for those claims? Did you read the Wikipedia link I provided? Where is this answer coming from? Did you use ChatGPT or some external resource to help you write this answer? $\endgroup$
    – D.W. ♦
    Commented Jan 24, 2023 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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