Counting quantifiers, successor relations, and logarithmic space

Given a successor relation S (i.e., a directed line graph), and given two distinguished points s and t, the problem ORD is to determine whether s precedes tin the unique ordering defined by S. We show that ORD is L-complete (via quantifier-free projections). We then show that first-order logic with counting quantifiers, a logic that captures TC0 over structures with a built-in total-ordering, cannot express ORD. Our original proof of this in the conference version of this paper employed an Ehrenfeucht-Fraisse Game for first-order logic with counting. Here we show how the result follows from a more general one obtained independently by Nurmonen. We then show that an appropriately modified version of the EF game is ''complete'' for the logic with counting in the sense that it provides a necessary and sufficient condition for I expressibility in the logic. We observe that the L-complete problem ORD is essentially sparse if we ignore reorderings of vertices, a property which We term ''pseudo-sparseness,'' We then prove that there are no pseudo-sparse NP-complete properties (under P-time reductions) unless the polynomial time hierarchy collapses (to Sigma(3)), revealing a structural property on which L and NP apparently differ. (C) 1997 Academic Press.