On the Computational Complexity of Incremental Algorithms
Ganesan Ramalingam, Thomas Reps · Minds at UW (University of Wisconsin) · 1991
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.