##
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]

### Abstract

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

TC^{0} 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