The simplex method works by walking along edges of a polytope toward the optimal vertex. At each step, it chooses a neighboring vertex that improves the objective. The method is fast in practice but no one has proved a polynomial worst-case bound. A natural question: how hard is it to find the shortest such walk?
Black and Steiner prove it is NP-hard. Computing a shortest monotone path to the optimum of a linear program over a simple polytope is computationally intractable, settling an open question from 2022. The result extends: finding optimal pivot sequences in the simplex method is also NP-hard, and determining a simple polytope's diameter — the longest shortest path between any two vertices — is NP-hard, resolving a problem open since 2003.
The constructive counterpart: all polytopes can be represented using extended formulations where linear-length paths between vertices can be found efficiently. The polytope itself makes short paths hard to find, but a lifted representation of the same polytope makes them easy. The hardness is not in the geometry but in the representation.
The through-claim is about the gap between existence and navigation. Short paths exist on these polytopes — the diameter is finite, the optimal vertex is reachable. But finding the shortest one among all possible walks requires solving a problem at least as hard as any in NP. The structure that guarantees the path exists does not help you find it efficiently. This is not the usual “the optimal solution exists but is hard to compute.” It is more specific: the optimal way to reach the optimal solution is itself the hard problem. The difficulty is not in the destination but in the route.