Simplex Methods and P problems

Question

I know that there are cases in which the simplex methods, in linear programming, needs exponential time to calculate the solution.

So why is simplex method considered a P problem ?

Answer 1

Linear Programming as such is in P because there are other algorithms which can solve Linear Programs (LPs) in polynomial time, for example interior points methods. The simplex, however, has an exponential running time for worst-case examples (such as the Klee-Minty-cube). Since other algorithms exist which can always solve an LP in polynomial time, LPs are in P.

Even though these worst-case examples for the simplex method exist, it shows very good running times in practice. One further advantage of the simplex method is that you can warm-start it if you have to make slight changes to your problem. This does not work with interior points methods which is why the simplex is often more attractive to use in practice, despite its potential exponential running time.