My question is; is all LP problems solvable in polynomial time?
I see an LP problem defined as follows,
maximize $~~c^Tx$
subject to
$~~~~~~~~~~Ax \leq b \\ ~~~~~~~~~~~~~x \geq 0$
where $A \in R^{m \times n}$.
I did some google search. I see simplex method is non-polynomial time algorithm, and interior point method takes $O((m+n)^{1.5}nL)$ arithmetic operations, where $L$ is a complicated quantity, roughly the log of the largest absolute value of the determinant of any square submatrix of A (more information here).