Given a polyhedron of the form $P=\lbrace x \in \mathbb{R}^n:x \geq 0, Ax=b \rbrace$, what is the arithmetic cost in order to determine whether the polyhedron is empty or not.
I know, that one can use Farkas to determine whether a system of linear inequalities has a solution or not, but I don't see, how this plays into the arithmetic cost.
Another idea I had is to use the simplex method an search for a feasible starting tableau. But this seems like quite a complicated approach.
Is there a more efficient one?