Editing Automatic differentiation (section)

=== Beyond forward and reverse accumulation ===

Forward and reverse accumulation are just two (extreme) ways of traversing the chain rule. The problem of computing a full Jacobian of {{math|''f'' : '''R'''<sup>''n''</sup> → '''R'''<sup>''m''</sup>}} with a minimum number of arithmetic operations is known as the ''optimal Jacobian accumulation'' (OJA) problem, which is [[NP-complete]].<ref>{{Cite journal|first=Uwe|last=Naumann|journal=Mathematical Programming|volume=112|issue=2|pages=427–441|date=April 2008|doi=10.1007/s10107-006-0042-z|title=Optimal Jacobian accumulation is NP-complete|citeseerx=10.1.1.320.5665|s2cid=30219572}}</ref> Central to this proof is the idea that algebraic dependencies may exist between the local partials that label the edges of the graph. In particular, two or more edge labels may be recognized as equal. The complexity of the problem is still open if it is assumed that all edge labels are unique and algebraically independent.