The data flow of a numerical program is reversed in its adjoint. We discuss the combinatorial optimization problem that aims
to find optimal checkpointing schemes at the level of call trees. For a given amount of persistent memory the objective is
to store selected arguments and/or results of subroutine calls such that the overall computational effort (the total number
of floating-point operations performed by potentially repeated forward evaluations of the program) of the data-flow reversal
is minimized. CALL TREE REVERSAL is shown to be NP-complete.
Keywords Adjoint code - call tree reversal - NP-completeness