\def \nrp {\hbox {\rm {\protect\small NRP}}} \def \poly {\hbox {\rm {\protect\small P}}} \def \nick {\hbox {\rm {\protect\small NC}}} \def \incrplt {\hbox {\rm {\it incr\/}\allowbreak-{\protect\small POLYLOGTIME}}} \def \logsp {\hbox {\rm {\protect\small LOGSPACE}}} \def \incrls {\hbox {\rm {\it incr\/}\allowbreak-{\protect\small LOGSPACE}}} \def \rincrls {\hbox {\rm {\it rincr\/}\allowbreak-{\protect\small LOGSPACE}}} \def \incrpls {\hbox {\rm {\it incr\/}\allowbreak-{\protect\small POLYLOGSPACE}}} \def \nlgsp{\hbox {\rm {\protect\small NLOGSPACE}}} 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 \logsp-complete problems for \poly\ are also \incrplt-complete for \poly. We introduce a restricted notion of completeness called $\nrp$-completeness and show that problems which are $\nrp$-complete for \poly\ are also \incrplt-complete for~\poly. We also give incrementally complete problems for \nlgsp, \logsp, and non-uniform ${\nick}^1$. We show that under certain restrictions problems which have efficient dynamic solutions also have efficient parallel solutions. We also consider a non-uniform 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 \incrls\ while the comparator-network stability and the ``Man-Optimal Stable Marriage Problem'''' are in $\rincrls(\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.