A Complexity Theoretic Approach to Incremental Computation

We present a new complexity theoretic approach to incremental computation. We define complexity classes that capture the intuitive notion of incremental efficiency and study their relation to existing complexity classes. We show that all common LOGSPACE-complete problems for P are incr-POLYLOGTIME-complete for P. This suggests that non-redundant problems that seem inherently unparallelizable also seem hard to dynamize. We show that a form of transitive closure is complete under incremental reduction for NLOGSPACE and give similar problems which are incrementally complete for the classes LOGSPACE and non-uniform NC¹. We show that under certain restrictions problems which have efficient dynamic solutions also have efficient parallel solutions. We also look at the time complexity of circuit value and network stability problems restricted to comparator gates. We show that the dynamic version of the comparatorcircuit value problem and "Lex-First Maximal Matching" problem is in LOGSPACE ..