Dynamic computational complexity
William Hesse, Neil Immerman · ScholarWorks@UMassAmherst (University of Massachusetts Amherst) · 2003
Dynamic computational complexity is the study of resource-bounded ongoing computational processes. We consider the general problem of processing a sequence of inputs, instead of a single input. We introduce a new model for dynamic computation, and investigate the computational complexity of various dynamic problems. The field of computational complexity has previously studied static computation, which takes a single fixed input and computes the desired result. We define a dynamic problem to be the function mapping a stream of data to the desired stream of output, and we investigate the complexity of the dynamic computation required to compute that function. We describe complexity classes of dynamic problems, reductions between dynamic problems, and complete problems for dynamic complexity classes.