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

Question

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?

Answer 1

Your problem is known as Linear Programming (if you change positive to non-negative). Usually linear programming is thought of as an optimization problem, but in fact the optimization problem is equivalent to feasibility, which is exactly what you're asking: whether a system of inequalities has any solution.

If you really want to ask whether there's a positive solution, then what you can do is take your system of inequalities $Ax \geq b$ and add the constraint $x_i \geq m$, maximizing over $m$. If the maximum is $m > 0$, then there is a strictly positive solution, otherwise there isn't.