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: computing deepest-descent steps is NP-hard and inapproximable even for 0/ 1 linear programs with a unique optimum which are defined by a totally unimodular constraint matrix .
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- \epsilon }) -approximating dd-steps remains hard even for totally unimodular n-dimensional 0/ 1 linear programs with a unique optimum which are defined by a totally unimodular constraint matrix .