Before revision:  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:  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 deciding the existence of an optimal circuit-neighbor problem (OCNP) for LPs with non-unique optima.