Counting Quantifiers, Successor Relations, and Logarithmic Space

摘要

Given a successor relationS(i.e., a directed line graph), and given two distinguished pointssandt, the problem ORD is to determine whethersprecedestin the unique ordering defined byS. 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 TC0over 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–Fraı̈ssé 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 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Σ3), revealing a structural property on which L and NP apparently differ.