H. Imhof Institut fur Mathematische Logik, Universitat Freiburg, Eckerstr. 1, D-79104 Freiburg, Germany. E-mail: firstname.lastname@example.org
The monotone circuit problem Q
MCis shown to be complete for fixed-point logic IFP under quantifier-free reductions. Enhancing the circuits with an oracle Q leads to a problem complete for IFP(Q). By contrast, if [Sigma] is any extension of FO with generalized quantifiers, one can always find a Q such that IFP(Q) is not contained in [Sigma](Q). For [Sigma] = FO(Q MC), we have [Sigma] [equivalent to] IFP but [Sigma](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 adjunction of further quantifiers, similar results as for IFP are proved. On ordered structures, where our results still hold, this reads as follows: for any given oracle Q, the complexity class PTIMEQ (or 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 [Sigma] that satisfies [Sigma](Q) [equivalent to] PTIMEQ (or PSPACEQ) for all Q. We also study second-order logic. Each level [Sigma] iof the polynomial hierarchy has a complete circuit problem. Closing FO under this problem does not exceed [Sigma] i+1. Hence, the polynomial hierarchy collapses to a certain level if and only if there is a class Q such that SO [equivalent to] FO(Q) holds on finite structures.
Keywords: Finite model theory, complexity theory, generalized quantifiers, oracles
Part of the OUP Journal of Logic and Computation WWW service
Click here to register with OUP.
This page is maintained by OUP admin
Part of the OUP Journals World Wide Web service.
Last modification: 22 Jul 1997
Copyright© Oxford University Press, 1997.