On the Expressive Power of Finitely many Generalized Quantifiers

Fixed point logics extended with generalized quantifiers have been studied widely in the last few years. One direction has been to examine if such logics can capture complexity classes. In a significant paper, among other results, Dawar and Hella showed that these logics can not capture PTIME on the class of cliques.

For each structure (and an integer k) one can define the number of k-automorphism types realized in this structure. Using this for any class of structures, growth rates of number of automorphism types for structures in the class can be defined as functions of size of the structures. For instance, for the class of cliques these growth rates are bounded by constant functions.

In this talk, I will describe a powerful extension of the result mentioned above by showing that PFP (partial fixed point logic) extended with finitely many generalized quantifiers, can not capture PSPACE on any (recursively enumerable) class of structures which has growth functions slower than "polynomials". Our Proof depends on the simple ideas of evaluating a fixpoint formula with generalized quantifiers efficiently on structures with few automorphism types. Using the same techniques, we can get other interesting results such as, on the class of complete binary trees IFP extended with finitely many generalized quantifiers, can not capture PTIME.

LS Home page or Talks in 1998/99