Fixed-point logics, generalized quantifiers, and oracles
H. Imhof · Journal of Logic and Computation · 1997
The monotone circuit problem QMC is shown to be complete for fixed-point IFP under quantifier-free reductions. Enhacing the circuits with an oracle Q leads to a problem complete for IFP(Q). By contrast, if L is any extension of FO with generalized quantifiers, one can always find a Q such that IFP(Q) is not contained in L(Q). For L = FO(QMC), we have L ≡ IFP but L(Q) ≤ IFP(Q). The adjunction of Q reveals the difference between these two representations of the class of IFP-definable queries. Also for partial fixed-point logic, PFP. a complete problem based on circuits is given, and, concerning the adjuction of futher quantifers, similar results as for IFP are proved. On ordered structures, where our results still hold, this reads as follows: for any guven oracle Q. the complexity class PTIMEQ (pr PSPACEQ in a bounded oracle model) can be characterized by an extension of FO with a uniform sequence of quantifiers. However, there is no such logic L that satisfies L(Q) ≡ PTIMEQ(or PSPACEQ) for all Q. We also study second-order logic. Each level Σi of the polynomial has a complete circuit problem. Closing FO under this problem does not exceed Σi+1. Hence, the polynomial hierarchy collapses to a certain level if and only if there is a class Q such that SO ≡ FO(Q) holds on finite structures.