Before revision:  However, the non-uniqueness assumption is crucial to the hardness of OCNP, because we show that OCNP for LPs with a unique optimum is solvable in polynomial time. Moreover, in practical applications one is usually only interested in finding some optimum of an LP, in which case a simple perturbation of the objective yields an instance with a unique optimum. It is thus natural to ask whether deepest-descent steps are also easy to compute for LPs with unique optima, or whether this problem is hard despite OCNP being easy. 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 prove OCNP is easy under the promise of unique optima, but already 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: