Journal of the Association for Computing Machinery, Vol. 44, No. 1, January 1997, pp. 30–56.

Fixpoint Logics, Relational Machines, and Computational Complexity

SERGE ABITEBOUL

MOSHE Y. VARDI

AND

VICTOR VIANU

Abstract. We establish a general connection between fixpoint logic and complexity. On one side, we have fixpoint logic, parameterized by the choices of 1st-order operators (inflationary or noninflationary) and iteration constructs (deterministic, nondeterministic, or alternating). On the other side, we have the complexity classes between P and EXP-TIME. Our parameterized fixpoint logics capture the complexity classes P, NP, PSPACE, and EXPTIME, but equality is achieved only over ordered structures.

There is, however, an inherent mismatch between complexity and logic—while computational devices work on encodings of problems, logic is applied directly to the underlying mathematical structures. To overcome this mismatch, we use a theory of relational complexity, which bridges the gap between standard complexity and fixpoint logic. On one hand, we show that questions about containments among standard complexity classes can be translated to questions about containments among relational complexity classes. On the other hand, the expressive power of fixpoint logic can be precisely characterized in terms of relational complexity classes. This tight, three-way relationship among fixpoint logics, relational complexity and standard complexity yields in a uniform way logical analogs to all containments among the complexity classes P, NP, PSPACE, and EXPTIME. The logical formulation shows that some of the most tantalizing questions in complexity theory boil down to a single question: the relative power of inflationary vs. noninflationary 1st-order operators.

Categories and Subject Descriptors. F.1.1 [Computation by Abstract Devices]: Models of Computation—bounded-action devices; random access machines; computability theory; relations among models; F.1.3 [Computation by Abstract Devices]: Complexity Classes—relations among complexity classes; relations among complexity measures; F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic—computational logic; H.2.3 [Database Management]: Languages—query languages

General Terms. Algorithms, Theory

Additional Key words and Phrases. Complexity classes, computational complexity, fixpoint logic, relational complexity

Copyright 1997 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.