On the Computational Complexity of Incremental Algorithms - Ramalingam, G.; Reps, Thomas (University of Wisconsin-Madison, Computer Sciences Department, 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 classiﬁed 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.