  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.
