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} $$

  • 1
    $\begingroup$ This seems to depend on the method used to solve the LP. $\endgroup$ – mvw May 9 '16 at 4:17
  • $\begingroup$ There must be a order of complexity for the best/common methods; right? $\endgroup$ – Daniel May 9 '16 at 15:31
  • $\begingroup$ It seems complicated. The simplex method runs down to inspecting vertices. While one can construct simplexes with $2^m$ vertices, thus exponential complexity, in practice it seems to be competetive with other methods. $\endgroup$ – mvw May 9 '16 at 16:04
  • 1
    $\begingroup$ Doesn't it depend on the model of computation? I vaguely recall reading that LP was in P if one used real RAM, but in NP if one used Turing machines. $\endgroup$ – Rodrigo de Azevedo Feb 23 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.