Volume 7: January - December 1997

Issue 3: 1997


Fixed-point logics, generalized quantifiers, and oracles

  • Fixed-point logics, generalized quantifiers, and oracles
  • H. Imhof

    Institut fur Mathematische Logik, Universitat Freiburg, Eckerstr. 1, D-79104 Freiburg, Germany. E-mail: imhof@sun1.mathematik.uni-freiburg.de


    The monotone circuit problem QMC is 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(QMC), 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]i of 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

    Pages: 405 - 525

    Part of the OUP Journal of Logic and Computation WWW service

    General Information

    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.