We present the first complete problems for dynamic
complexity classes including the classes DynFO and DynTC^0,
the dynamic classes corresponding to relational calculus and
(polynomially bounded) SQL, respectively. The first problem we show
complete for DynFO 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 complete for all first-order
formulas. As a corollary we obtain a fixed quantifier block, QBC,
that is complete for all first-order quantifier blocks.
