# What is the computational complexity of linear programming?

What is the computational complexity of solving a linear program with $$m$$ constraints in $$n$$ variables?

• There are (weak)polynomial times algorithms that find the solutions by moving a point in the interior of the simplex. I don't know what is the minimum exponent possible. – user647486 Apr 26 '19 at 17:53
• Though it’s worth mentioning that the most common linear programming algorithm—the simplex—method, os exponential in its worst case. – David M. Apr 28 '19 at 3:43
• Thank you, but here I am speaking about the theoretical complexity of linear programming not algorithms. For example, it is known (to the best of my knowledge) that solving a quadratic program is equivalent to solving a system of linear equations, so the complexity of quadratic programming is about O(n^3). Is there any similar result for linear programming ? – user486789 Apr 28 '19 at 17:40