#
The Simplex Algorithm is NP-Mighty

##
Will Devanny

We propose to classify the power of algorithms by the complexity of the
problems that they can be used to solve. Instead of restricting to the
problem a particular algorithm was designed to solve explicitly, however, we
include problems that, with polynomial overhead, can be solved ‘implicitly’
during the algorithm’s execution. For example, we allow to solve a decision
problem by suitably transforming the input, executing the algorithm, and
observing whether a specific bit in its internal configuration ever switches
during the execution.
We show that the Simplex Method, the Network Simplex Method (both with
Dantzig’s original pivot rule), and the Successive Shortest Path Algorithm
are NP-mighty, that is, each of these algorithms can be used to solve any
problem in NP. This result casts a more favorable light on these
algorithms’ exponential worst-case running times. Furthermore, as a
consequence of our approach, we obtain several novel hardness results. For
example, for a given input to the Simplex Algorithm, deciding whether a
given variable ever enters the basis during the algorithm’s execution and
determining the number of iterations needed are both NP-hard problems.
Finally, we close a long-standing open problem in the area of network flows
over time by showing that earliest arrival flows are NP-hard to obtain.

This paper was presented at SODA 2015.