Complexity models for 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 problems that have small sequential space complexity also have small incremental time complexity. We show that all common LOGSPACE-complete problems for P are also incr-POLYLOGTIME-complete for P. We introduce a restricted notion of completeness called NRP-completeness and show that problems which are NRP-complete for P are also incr-POLYLOGTIME-complete for P. We also give incrementally complete problems for NLOGSPACE, LOGSPACE, and nonuniform NC1. We show that under certain restrictions problems which have efficient dynamic solutions also have efficient parallel solutions. We also consider a nonuniform model of incremental computation and show that in this model most problems have almost linear complexity. In addition, we present some techniques for lower bounding the complexity of explicitly defined problems. We also look at the time complexity of circuit-value and network-stability problems restricted to comparator gates. We show that the comparator-circuit value problem and the “lex-first maximal matching” problem are in incr-LOGSPACE while the comparator-network stability and the “man-optimal stable marriage problem” are in rincr-LOGSPACE(NLOGSPACE). This shows that the dynamic versions of these problems are solvable quickly in parallel even though there are no known NC algorithms to solve them from scratch.

Authors

• Peter Bro Miltersen
• Sairam Subramanian
• Jeffrey Scott Vitter
• Roberto Tamassia

Keywords

No keywords are indexed for this paper.