Fixpoint logics, relational machines, and computational complexity

To overcome the inherent mismatch between complexity and logic, i.e., that while computational devices work on encodings of problems, logic is applied directly to the underlying mathematical structures, the authors develop a theory of relational complexity that bridges the gap between standard complexity and fixpoint logic. It is shown that questions about containments among standard complexity classes can be translated to questions about containments among relational complexity classes, and that 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