**Abstract:**
We present the first complete problems for dynamic complexity classes
including the classes Dyn-FO and DynThC^{0},
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