Before revision: Linear programs (LPs) can be solved through a polynomial number of so-called deepest-descent circuit steps, each step following a circuit direction to a new feasible solution of most-improved objective function value. A computation of deepest-descent steps has recently been shown to be NP-hard  De Loera et al., arXiv, 2019 . This is a consequence of the hardness of what we call the optimal circuit-neighbor problem (OCNP) for LPs with non-unique optima.
After revision: Linear programs (LPs) can be solved through a polynomial number of so-called deepest-descent steps has recently been shown to be NP-hard De Loera et al., arXiv, 2019 . This is a consequence of the hardness of what we call the optimal circuit-neighbor problem (OCNP) for LPs with non-unique optima.