Traditional complexity theory deals with decision problems, that read an input and decide whether to accept or reject that input. However, many modern applications of computers are ongoing computational processes that continually receive updates and answer queries. These have been studied by researchers working on dynamic algorithms and dynamic data structures.
We define dynamic problems and dynamic complexity classes analogous to the standard model of decision problems and complexity classes, and investigate their properties. We find reductions between dynamic problems, and problems that are complete for dynamic complexity classes under those reductions. We also describe new algorithms for dynamic transitive closure and its variants. These algorithms use restricted models of dynamic computation, and place these problems in small dynamic complexity classes.
Last modified 10 February 2003