4
$\begingroup$

How to determine whether a system of linear inequalities has a positive solution or not?

Is there any poly-time algorithm to do this? Or the best algorithms known are no less complex than algorithms for solving set of linear inequalities?

  • 0
    Question posted at mathoverflow and was closed. Don't remember the link.2012-01-15
  • 1
    Note that search for positive solutions can be written as another general linear inequality because $x_i>0$ is just a linear inequality, so you can add it to your system and you still have a system of linear equalities.2012-01-15
  • 0
    @Benjamin: Two versions at MO were posted: [This one](http://mathoverflow.net/questions/85731/how-to-determine-whether-a-system-of-linear-inequalities-has-a-positive-solution) and [this one](http://mathoverflow.net/questions/85669/how-to-determine-whether-a-system-of-linear-inequalities-has-a-solution-or-not). They were both closed there. But, they're clearly on-topic here.2012-01-15

1 Answers 1