Logic in Computer Science (LICS 2002)

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 Symp. on Logic in Computer Science, {LICS} 2002},
    year =	 2002,
    editor =	 {Gordon Plotkin},
    month =	 {July}, 
    location =   {Copenhagen, Denmark}, 
    publisher =	 {IEEE Computer Society Press}
  }