Counting and Addition cannot express Deterministic Transitive Closure

Matthias Ruhl

IEEE Symposium on Logic in Computer Science (LICS '99)
Trento, July 1999

[Postscript, 155KB]

[PDF, 143KB]


An important open question in complexity theory is whether the circuit complexity class TC0 is (strictly) weaker than LOGSPACE. This paper considers this question from the viewpoint of descriptive complexity theory.

TC0 can 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.

Back to publications