Complete problems for Dynamic Complexity Classes

William Hesse and Neil Immerman

To appear at Symposium on Logic in Computer Science (LICS'2002), Copenhagen, Denmark, July 22nd - 25th, 2002


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.

Server START Conference Manager
Update Time 15 Mar 2002 at 15:30:31
Start Conference Manager
Conference Systems