Abstract: We present the first complete problems for dynamic complexity classes including the classes Dyn-FO and DynThC0, the dynamic classes corresponding to relational calculus and (polynomially bounded) SQL, respectively. The first problem we show complete for Dyn-FO is a single-step version of the circuit value problem (SSCV).
Of independent interest, our construction also produces a first-order
formula, 
, that is in a sense universal for all first-order
formulas. Since first-order formulas are stratified by quantifier depth,
the first-order formula emulates formulas of greater depth by
iterated application. As a corollary we obtain a fixed quantifier block,
QBC,
that is complete for all first-order quantifier blocks.
Recent Publications of Neil Immerman