Relativized logspace and generalized quantifiers over finite structures
Georg Gottlob · 2002
The expressive power of first order logic with generalized quantifiers over finite ordered structures is studied. The following problem is addressed: Given a family Q of generalized quantifiers expressing a complexity class C, what is the expressive power of first order logic FO(Q) extended by the quantifiers in Q? From previously studied examples, one would expect that FO(Q) captures L/sup C/, i.e., logarithmic space relativized by an oracle in C. We show that this is not always true. However, we derive sufficient conditions on complexity class C such that FO(and) captures L/sup C/. These conditions are fulfilled by a large number of relevant complexity classes, in particular, for example, by NP. As an application of this result, it follows that first order logic extended by Henkin quantifiers captures L/sup NP/. This answers a question raised by Blass and Gurevich. Furthermore we show that for many families Q of generalized quantifiers (including the family of Henkin quantifiers), each FO(Q)-formula can be replaced by an equivalent FO(Q)-formula, with only two occurrences of generalized quantifiers.