The Complexity of Derivative Computation

Uwe Naumann

We show that the problem of accumulating Jacobian matrices by using a
minimal number of floating-point operations is NP-complete by reduction
from Ensemble Computation. The proof makes use of the fact that, deviating
from the state-of-the-art assumption, algebraic dependences can exist
between the local partial derivatives.  It follows immediately that the
same problem for directional derivatives, adjoints, scalar, and higher
derivatives is NP-complete too.