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 ?
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.