On the Computational Complexity of Incremental Algorithms

Our results, together with some previously known ones, shed light on the organization of the complexity hierarchy that exists when incremental-computation problems are classified according to their incremental complexity with respect to locally persistent algorithms. In particular, these results separate the classes of P-time incremental problems, inherently Exp~ time incremental problems, and non-incremental problems.