Tech Report CS-91-66

A Complexity-Theoretic Approach to Incremental Computation

S. Sairam, Jeffrey Scott Vitter and Roberto Tamassia

December 1991

Abstract:

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 logs p-complete problems for poly are incrplt-complete for poly. 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 nlgsp and give similar problems which are incrementally complete for the classes logsp and non-uniform nick. 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 comparator-circuit value problem and ``Lex-First Maximal Matching'' problem is in logsp and that of the comparator-network stability problem and ``Man-Optimal Stable Marriage Problem'' is in logsp given an oracle which operates in nlgsp. This shows that the dynamic versions of these problems are solvable quickly in parallel even though there are no known nick algorithms to solve them from scratch.

(complete text in pdf or gzipped postscript)