Logic in Computer Science (LICS 1999)

Paper: Counting and Addition cannot Express Deterministic Transitive Closure (at LICS 1999)

Authors: Matthias Ruhl

Abstract

An important open question in complexity theory is whether the circuit complexity class \mathis (strictly) weaker than LOGSPACE. This paper considers this question from the viewpoint of descriptive complexity theory. \mathcan be characterized as the class of queries expressible by the logic FOC(<,+,*), which is first-order logic augmented by counting quantifiers on ordered structures that have addition and multiplication predicates. We show that in first-order logic with counting quantifiers and only an addition predicate it is not possible to express "deterministic transitive closure" on ordered structures. As this is a LOGSPACE-complete problem, this logic therefore fails to capture LOGSPACE. It also directly follows from our proof that in the presence of counting quantifiers, multiplication cannot be expressed in terms of addition and ordering alone.

BibTeX

  @InProceedings{Ruhl-CountingandAddition,
    author = 	 {Matthias Ruhl},
    title = 	 {Counting and Addition cannot Express Deterministic Transitive Closure},
    booktitle =  {Proceedings of the Fourteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1999},
    year =	 1999,
    editor =	 {Giuseppe Longo},
    month =	 {July}, 
    pages =      {326--334},
    location =   {Trento, Italy}, 
    publisher =	 {IEEE Computer Society Press}
  }