FIXPOINT LOGICS, RELATIONAL MACHINES, AND COMPUTATIONAL-COMPLEXITY

We establish a general connection between fixpoint logic and complexit y. On one side, we have fixpoint logic, parameterized by the choices o f 1st-order operators (inflationary or noninflationary) and iteration constructs (deterministic, nondeterministic, or alternating). On the o ther side, we have the complexity classes between P and EXPTIME. Our p arameterized fixpoint logics capture the complexity classes P, NP, PSP ACE, and EXPTIME, but equality is achieved only over ordered structure s. There is, however, an inherent mismatch between complexity and logi c-while computational devices work on encodings of problems, logic is applied directly to the underlying mathematical structures. To overcom e this mismatch, we use a theory of relational complexity, which bridg es 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 relati onal complexity classes. On the other hand, the expressive power of fi xpoint logic can be precisely characterized in terms of relational com plexity classes. This tight, three-way relationship among fixpoint log ics, 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 si ngle question: the relative power of inflationary vs. noninflationary 1st-order operators.