Computational complexity of a feasibility LP with $m$ inequalities, in $d$ dimension?

78 Views Asked by At

How would you quantify the computational complexity of feasibility LPs? Say, for example, an LP with $m$ inequalities:

$$ \begin{cases} \mathbf{a_i} \cdot \mathbf{x} \leq b_i, \quad i \in [m] \\ \mathbf{x} \in \mathbb{R}^d \end{cases} $$