Journal of the ACM Bibliography

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 EXPTIME. 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.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

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

Selected papers that cite this one

• Serge Abiteboul, Christos H. Papadimitriou, and V. Vianu. Reflective relational machines. Information and Computation, 143(2):110-136, 15 June 1998.

• Anuj Dawar. A restricted second order logic for finite structures. Information and Computation, 143(2):154-174, 15 June 1998.

• Detlef Seese. Linear time computable problems and first-order descriptions. Mathematical Structures in Computer Science, 6(6):505-526, December 1996.

Selected references

• Serge Abiteboul, Eric Simon, and Victor Vianu. Non-deterministic languages to express deterministic transformations. In Proceedings of the Nith ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 218-229, Nashville, Tennessee, 2-4 April 1990.

• Serge Abiteboul and Victor Vianu. Fixpoint extensions of first-order logic and Datalog-like languages. In Proceedings, Fourth Annual Symposium on Logic in Computer Science, pages 71-79, Asilomar Conference Center, Pacific Grove, California, 5-8 June 1989. IEEE Computer Society Press.

• Serge Abiteboul and Victor Vianu. Datalog extensions for database queries and updates. Journal of Computer and System Sciences, 43(1):62-124, August 1991.

• Serge Abiteboul and Victor Vianu. Generic computation and its complexity. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 209-219, New Orleans, Louisiana, 6-8 May 1991.

• Serge Abiteboul and Victor Vianu. Computing with first-order logic. Journal of Computer and System Sciences, 50(2):309-335, April 1995.

• Serge Abiteboul, Moshe Y. Vardi, and Victor Vianu. Computing with infinitary logic. Theoretical Computer Science, 149(1):101-128, 18 September 1995.

• Alfred V. Aho and Jeffrey D. Ullman. The universality of data retrieval languages. In Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, pages 110-120, San Antonio, Texas, January 1979.

• Ashok K. Chandra and David Harel. Computable queries for relational data bases. Journal of Computer and System Sciences, 21(2):156-178, October 1980.

• Ashok Chandra and David Harel. Structure and complexity of relational queries. Journal of Computer and System Sciences, 25(1):99-128, August 1982.

• Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer. Alternation. Journal of the ACM, 28(1):114-133, January 1981.

• Kevin L. Compton and Claude Laflamme. An algebra and a logic for NC^1. In Proceedings, Third Annual Symposium on Logic in Computer Science, pages 12-21, Edinburgh, Scotland, 5-8 July 1988. IEEE Computer Society.

• Anuj Dawar, Steven Lindell, and Scott Weinstein. Infinitary logic and inductive definability over finite structures. Information and Computation, 119(2):160-175, June 1995.

• Andreas Goerdt. Characterizing complexity classes by higher type primitive recursive definitions. In Proceedings, Fourth Annual Symposium on Logic in Computer Science, pages 364-374, Asilomar Conference Center, Pacific Grove, California, 5-8 June 1989. IEEE Computer Society Press.

• Erich Grädel and Gregory L. McColm. Hierarchies in transitive closure logic, stratified datalog and infinitary logic. In 33rd Annual Symposium on Foundations of Computer Science, pages 167-176, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

• Erich Grädel and Gregory L. McColm. Deterministic vs.\ nondeterministic transitive closure logic. In Proceedings, Seventh Annual IEEE Symposium on Logic in Computer Science, pages 58-63, Santa Cruz, California, 22-25 June 1992. IEEE Computer Society Press.

• Etienne Grandjean. The spectra of first-order sentences and computational complexity. SIAM Journal on Computing, 13(2):356-373, May 1984.

• Martin Grohe. Equivalence in finite-variable logics is complete for polynomial time. In 37th Annual Symposium on Foundations of Computer Science, pages 264-273, Burlington, Vermont, 14-16 October 1996. IEEE.

• Yuri Gurevich. Algebras of feasible functions. In 24th Annual Symposium on Foundations of Computer Science, pages 210-214, Tucson, Arizona, 7-9 November 1983. IEEE.

• D. Harel and D. Peleg. On static logics, dynamic logics, and complexity classes. Information and Control, 60(1-3):86-102, January/February/March 1984.

• Neil Immerman. Upper and lower bounds for first order expressibility. Journal of Computer and System Sciences, 25(1):76-98, August 1982.

• Neil Immerman. Relational queries computable in polynomial time. Information and Control, 68(1-3):86-104, January/February/March 1986.

• Neil Immerman. Languages that capture complexity classes. SIAM Journal on Computing, 16(4):760-778, August 1987.

• Phokion G. Kolaitis and Moshe Y. Vardi. On the expressive power of Datalog: Tools and a case study. Journal of Computer and System Sciences, 51(1):110-134, August 1995.

• Phokion G. Kolaitis and Moshe Y. Vardi. Infinitary logics and 0-1 laws. Information and Computation, 98(2):258-294, June 1992.

• Daniel Leivant. Descriptive characterizations of computational complexity. Journal of Computer and System Sciences, 39(1):51-83, August 1989.

• Daniel Leivant. Inductive definitions over finite structures. Information and Computation, 89(2):95-108, December 1990.

• Daniel Leivant. A foundational delineation of computational feasiblity. In Proceedings, Sixth Annual IEEE Symposium on Logic in Computer Science, pages 2-11, Amsterdam, The Netherlands, 15-18 July 1991. IEEE Computer Society Press.

• Steven Lindell. An analysis of fixed-point queries on binary trees. Theoretical Computer Science, 85(1):75-95, 5 August 1991.

• Michel de Rougemont. Uniform definability on finite structures with successor. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pages 409-417, Washington, D.C., 1984.

• Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177-192, April 1970.

• Thomas Schwentick. Graph connectivity and monadic NP. In 35th Annual Symposium on Foundations of Computer Science, pages 614-622, Santa Fe, New Mexico, 20-22 November 1994. IEEE.

• Larry J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3(1):1-22, October 1976.

• Jerzy Tiuryn and Pawe{\l} Urzyczyn. Some relationships between logics of programs and complexity theory. Theoretical Computer Science, 60(1):83-108, March 1988. Fundamental Study.

• Moshe Y. Vardi. The complexity of relational query languages (extended abstract). In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 137-146, San Francisco, California, 5-7 May 1982.

Shortcuts: