The following technical report is available from http://aib.informatik.rwth-aachen.de/:

The Complexity of Derivative Computation Uwe Naumann AIB 2005-15

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.