H .Imhof

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

ABSTRACT The monotone circuit problem

Qis shown to be complete for fixed-point logic IFP under quantifier-free reductions. Enhancing the circuits with an oracleMC Qleads to a problem complete forIFP(Q). By contrast, if [Sigma] is any extension ofFOwith generalized quantifiers, one can always find aQsuch thatIFP(Q)is not contained in [Sigma](Q). For [Sigma] =FO(Q), we have [Sigma] [equivalent to]MC IFPbut [Sigma](Q). The adjunction ofQreveals the difference between these two representations of the class ofIFP-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 forIFPare proved. On ordered structures, where our results still hold, this reads as follows: for any given oracleQ, the complexity classPTIME(or^{Q}PSPACEin a bounded oracle model) can be characterized by an extension of^{Q}FOwith a uniform sequence of quantifiers. However, there is no such logic [Sigma] that satisfies [Sigma](Q) [equivalent to]PTIME(or^{Q}PSPACE) for all^{Q}Q. We also study second-order logic. Each level [Sigma]i of the polynomial hierarchy has a complete circuit problem. ClosingFOunder this problem does not exceed [Sigma]i+1 . Hence, the polynomial hierarchy collapses to a certain level if and only if there is a classQsuch thatSO[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

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.