Dyn-FO: A Parallel, Dynamic Complexity Class

摘要

Traditionally, computational complexity has considered only static problems. Classical complexity classes such as NC, P, and NP are defined in terms of the complexity of checking—upon presentation of an entire input—whether the input satisfies a certain property. For many applications of computers it is more appropriate to model the process as a dynamic one. There is a fairly large object being worked on over a period of time. The object is repeatedly modified by users and computations are performed. We develop a theory of dynamic complexity. We study the new complexity class, dynamic first-order logic (Dyn-FO). This is the set of properties that can be maintained and queried in first-order logic, i.e., relational calculus, on a relational database. We show that many interesting properties are in Dyn-FO, including multiplication, graph connectivity, bipartiteness, and the computation of minimum spanning trees. Note that none of these problems is in static FO, and this fact has been used to justify increasing the power of query languages beyond first-order. It is thus striking that these problems are indeed dynamic first-order and, thus, were computable in first-order database languages all along. We also define “bounded-expansion reductions” which honor dynamic complexity classes. We prove that certain standard complete problems for static complexity classes, such as REACHafor P, remain complete via these new reductions. On the other hand, we prove that other such problems, including REACH for NL and REACHdfor L, are no longer complete via bounded-expansion reductions. Furthermore, we show that a version of REACHa, called REACHa+, is not in Dyn-FO unless all of P is contained in parallel linear time.