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 give problems that are complete for P, NLOGSPACE, and LOGSPACE under incremental reductions. 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 look at the incremental space-complexity of circuit value and network stability problems restricted to comparator gates. We show that the dynamic version of the comparator circuit value problem is in LOGSPACE while the dynamic version of the network stability problem can be solved in LOGSPACE given an NLOGSPACE oracle. This shows that problems like the Lex-First Maximal Matching problem and the Man-Optimal Stable Marriage problem can be quickly updated in parallel even though there are no known NC algorithms to solve them from scratch.
Research supported in part by a National Science Foundation Presidential Young Investigator Award CCR-9047466 with matching funds from IBM, by NSF research grant CCR-9007851, by Army Research Office grant DAAL03-91-G-0035, and by the Office of Naval Research and the Defense Advanced Research Projects Agency under contract N00014-91-J-4052 and ARPA order 8225.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Barrington, “Bounded Width Polynomial Size Programs Recognize Exactly Those Languages in NC 1,” Proc. 18th Symposium on Theory of Computing (1986), 1–5.
A. M. Berman, M. C. Paul, and B. G. Ryder, “Proving Relative Lower Bounds for Incremental Algorithms,” Acta Informatica 27(1990), 665–683.
A. Delcher and S. Kasif, “Complexity Issues in Parallel Logic Programming,” Johns Hopkins University, Ph.D Thesis, 1989.
R. Greenlaw, H. J. Hoover, and W. L. Ruzzo, “A Compendium of Problems Complete for P,” Department of Computer Science and Engineering, University of Washington, Technical Report TR-91-05-01, 1991.
L.J. Guibas and R. Sedgewick, “A Dichromatic Framework for Balanced Trees,” Proc. 19th IEEE Symposium on Foundations of Computer Science (1978), 8–21.
R.M. Karp and V. Ramachandran, “A Survey of Parallel Algorithms for Shared Memory Machines,” in Handbook of Theoretical Computer Science, North Holland, 1990, 871–941.
R. E. Ladner, “The Circuit Value Problem is Log Space Complete for P,” SIGACT News 7(1975), 18–20.
E. Mayr and A. Subramanian, “The Complexity of Circuit Value and Network Stability,” Proc. 4th Annual Conference on Structure in Complexity Theory (1989), 114–123.
K. Mehlhorn and M. Overmars, “Optimal Dynamization of Decomposable Searching Problems,” Information Processing Letters 12(1981), 93–98.
P. B. Miltersen, “On-line reevaluation of functions,” Computer Science Dept, Aarhus University, Aarhus DK., Technical Report ALCOM-91-63, May 1991.
S. Miyano, S. Shiraishi, and T. Shoudai, “A List of P-Complete Problems,” Research Institute of Fundamental Information Science, Kyushu, Research Report, 1989.
M. Overmars, “The Design of Dynamic Data Structures,” Lecture Notes in Computer Science 156(1983).
J.H. Reif, “A Topological Approach to Dynamic Graph Connectivity,” Information Processing Letters 25 (1987), 65–70.
S. Skyum and L. G. Valiant, “A Complexity Theory Based on Boolean Algebra,” Proc. 22nd IEEE Symposium on Foundations of Computer Science (1981), 244–253.
A. Subramanian, “A New Approach to Stable Matching Problems,” Department of Computer Science, Stanford University, Technical Report STAN-CS-89-1275, 1989.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sairam, S., Vitter, J.S., Tamassia, R. (1993). A complexity theoretic approach to incremental computation. In: Enjalbert, P., Finkel, A., Wagner, K.W. (eds) STACS 93. STACS 1993. Lecture Notes in Computer Science, vol 665. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56503-5_63
Download citation
DOI: https://doi.org/10.1007/3-540-56503-5_63
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56503-1
Online ISBN: 978-3-540-47574-3
eBook Packages: Springer Book Archive