Fixpoint logics, relational machines, and computational complexity
- 2 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 156-168
- https://doi.org/10.1109/sct.1992.215391
Abstract
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.<>Keywords
This publication has 33 references indexed in Scilit:
- A foundational delineation of computational feasibilityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- 0-1 laws for infinitary logicsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Inductive definitions over finite structuresInformation and Computation, 1990
- Describing Graphs: A First-Order Approach to Graph CanonizationPublished by Springer Nature ,1990
- Descriptive characterizations of computational complexityJournal of Computer and System Sciences, 1989
- Descriptive and computational complexityProceedings of Symposia in Applied Mathematics, 1989
- Languages that Capture Complexity ClassesSIAM Journal on Computing, 1987
- Relational queries computable in polynomial timeInformation and Control, 1986
- On static logics, dynamic logics, and complexity classesInformation and Control, 1984
- Turing machines and the spectra of first-order formulas with equalityPublished by Association for Computing Machinery (ACM) ,1972