Paper: Complete problems for Dynamic Complexity Classes (at LICS 2002)
Authors: William Hesse Neil Immerman
Abstract
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.
BibTeX
@InProceedings{HesseImmerman-Completeproblemsfor, author = {William Hesse and Neil Immerman}, title = {Complete problems for Dynamic Complexity Classes}, booktitle = {Proceedings of the Seventeenth Annual IEEE Symposium on Logic in Computer Science (LICS 2002)}, year = {2002}, month = {July}, pages = {313--322}, location = {Copenhagen, Denmark}, publisher = {IEEE Computer Society Press} }