This question is about designing a polynomial time algorithm for linear programming given access to an oracle outputs YES if and only if $\{\vec{x}\ |\ A\vec{x} = \vec{b}, \vec{x}\geqslant \vec{0}\}\neq \emptyset$.
The linear programming is of the following form: $$\min\ \vec{c}^T\vec{x}\ \text{ subject to }\ A\vec{x}\geqslant \vec{b},\ \vec{x}\geqslant \vec{0} $$
Each query to the oracle cost one time step. Any help will be appreciated! Thanks in advance!
This is not a complete answer - more of a pointer, if even that. Since you have an oracle that only tells you if a formulation has a solution, to use this to pinpoint an optimum I think you will need to use something like the Dual-Simplex method, where you stop once you get a Primal feasible solution. However, instead of having to actually run the simplex method, you can simply check feasibility at each step and then use the Dual formulation to adjust bounds on the constraints until you acheive Primal feasibility.