Before revision:  We show that deepest-descent steps can be efficiently approximated within a factor of n, where n is the dimension of the polyhedron at hand, but not within a factor of O(n^{1- \epsilon }) for any \epsilon > 0. While we prove that OCNP can be solved efficiently for LPs with a unique optimum, our different hardness approach allows us to show strong negative results:
After revision:  We show that deepest-descent steps can be efficiently approximated within a factor of n, where n is the dimension of the polyhedron at hand, but not within a factor of O(n^{1- \varepsilon }) for any \epsilon > 0. While we prove that OCNP can be solved efficiently for LPs with a unique optimum, our different hardness approach allows us to show strong negative results: