Linear Programming Confusion about Complexity

Question

In the wiki page of Linear Programming is told that Linear Programming problems belong to P complexity class.

However, the method generally used to solve Linear Programming problems is the Simplex method that not belong to P. So, does this make Linear Programming problems exponentially complex ?

the performance of the simplex algorithm may also greatly depend on the specific pivot rule used. simplex method has polynomial smoothed complexity. Please check: Complexity of the simplex algorithm — W.R.P.S, Jul 17 '18 at 07:55
As example Quick sort has worst complexity of $O(n^2)$ but it's still preferred instead of merge sort with $O(n\log n)$ worst complexity. — kingW3, Jul 17 '18 at 09:21

score 3 · Accepted Answer · answered Jul 17 '18 at 07:47

Linear Programming can be solved in polynomial time with ellipsoid algorithms.

However, in practice, the simplex algorithm is more efficient, despite the fact that its worst time run times are exponential.

So in summary : linear programming problems are not "exponentially complex", but they are typically solved with an algorithm that may run in exponential times in worst case scenarios.

Linear Programming Confusion about Complexity

1 Answers1