Fixpoint logics, relational machines, and computational complexity

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

REFERENCES

• 1: Serge Abiteboul , Eric Simon , Victor Vianu, Non-deterministic languages to express deterministic transformations, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.218-229, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298575]
• 2: Serge Abiteboul , Moshe Y. Vardi , Victor Vianu, Computing with infinitary logic, Theoretical Computer Science, v.149 n.1, p.101-128, Sept. 18, 1995
• 3: S. Abiteboul , V. Vianu, Fixpoint extensions of first-order logic and datalog-like languages, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.71-79, June 1989, Pacific Grove, California, United States
• 4: Serge Abiteboul , Victor Vianu, Datalog extensions for database queries and updates, Journal of Computer and System Sciences, v.43 n.1, p.62-124, Aug. 1991 [doi>10.1016/0022-0000(91)90032-Z]
• 5: Serge Abiteboul , Victor Vianu, Generic Computation and its complexity, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.209-219, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103444]
• 6: Serge Abiteboul , Victor Vianu, Computing with first-order logic, Journal of Computer and System Sciences, v.50 n.2, p.309-335, April 1995
• 7: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• 8: BARWISE, J. 1977. On Moschovakis closure ordinals. J. Symb. Logic 42, 292-296.
• 9: Buss, S.R., 1986. Bounded Arithmetics. Bibliopolis, Naples, Italy.
• 10: CHANDRA, A., AND HAREL, D. 1980. Computable queries for relational databases. J. Comput. Syst. Sci. 21, 156-178.
• 11: CHANDRA, A., AND HAREL, D. 1982. Structure and complexity of relational queries. J. Comput. Syst. Sci. 25, 99-128.
• 12: Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
• 13: CODD, E. F. 1972. Relational completeness of data base sublanguages. In Database Systems, R. Rustin, ed. Prentice-Hall, Englewood Cliffs, N.J., pp. 33-64.
• 14: COMPTON, K.J. 1988. An algebra and a logic for NC1. In Proceedings of the 3rd IEEE Symposium on Logic in Computer Science. IEEE, New York, pp. 12-21.
• 15: Anuj Dawar , Steven Lindell , Scott Weinstein, Infinitary logic and inductive definability over finite structures, Information and Computation, v.119 n.2, p.160-175, June 1995 [doi>10.1006/inco.1995.1084]
• 16: Michel de Rougemont, Uniform definability on finite structures with successor, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.409-417, December 1984 [doi>10.1145/800057.808707]
• 17: FAGIN, R. 1974. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation, SIAM-AMS Proceedings, Vol. 7. R. M. Karp, ed. American Mathematical Society, Providence, R.I. pp. 43-73.
• 18: FAGIN, R. 1975. Monadic generalized spectra. Z. Math. Logik Grundl. Math. 21, 89-96.
• 19: Tomás Feder , Donald E. Knuth, Stable networks and product graphs, Stanford University, Stanford, CA, 1992
• 20: FRIEDMAN, H. 1971. Axiomatic recursive function theory. In Logic Colloquium '69, R. O. Gandy and C. E. M. Yateb, eds. North-Holland, Amsterdam, The Netherlands, pp. 113-137.
• 21: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 22: GIRARD, J.-Y., SCEDROV, A., AND SCOTT, P. 1990. Bounded linear logic: A modular approach to polynomial time computability. In Feasible Mathematics, S. R. Buss and P. Scott, eds. Birkhauser, Boston, Mass., pp. 195-207.
• 23: A. Goerdt, Characterizing complexity classes by higher type primitive recursive definitions, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.364-374, June 1989, Pacific Grove, California, United States
• 24: GR)iDEL, E., AND MCCOLM, G. 1992a. Deterministic versus nondeterministic transitive closure logic. In Proceedings of the 7th IEEE Symposium on Logic in Computer Science. IEEE, New York, pp. 58-63.
• 25: GR)iDEL, E., AND MCCOLM, G. 1992b. Hierarchies in transitive closure logic, stratified datalog and infinitary logic. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science. IEEE New York, pp. 167-176.
• 26: GRANDJEAN, E. 1984. The spectra of first-order sentences and computational complexity. SIAM J. Comput. 13, 356-373.
• 27: GRANDJEAN, E. 1985. Universal quantifiers and time complexity of random access machines. Math. Syst. Theory 13, 171-187.
• 28: M. Grohe, Equivalence in finite-variable logics is complete for polynomial time, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.264, October 14-16, 1996
• 29: GUREVICH, Y. 1983. Algebras of feasible functions. In Proceedings of the 24th IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 210-214.
• 30: GUREVICH, Y. 1984. Toward logic tailored for computational complexity. In Computation and Proof Theory, M. M. Richter et al., eds. Lecture Notes in Mathematics, vol. 1104. Springer-Verlag, New York, pp. 175-216.
• 31: GUREVICH, Y. 1988. Logic and the challenge of computer science. In Current Trends in Theoretical Computer Science, E. B6rger, ed. Computer Science Press, Rockville, Md., pp. 1-57.
• 32: GUREVICH, Y., AND SHELAH, S. 1986. Fixed-point extensions of first-order logic. Ann. Pure Appl. Logic 32, 265-280.
• 33: HAREL, D., AND PELEG, D. 1984. Static logics, dynamic logics, and complexity classes. Inf. Cont. 60, 86-102.
• 34: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 35: IMMERMAN, N. 1982. Upper and lower bounds for first-order expressibility. J. Comput. Syst. Sci. 25, 76-98.
• 36: Neil Immerman, Relational queries computable in polynomial time, Information and Control, v.68 n.1-3, p.86-104, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80029-8]
• 37: IMMERMAN, N. 1987a. Expressibility as a complexity measure: Results and directions. In Proceedings of the 2nd Structure in Complexity Conference. IEEE, New York, pp. 194-202.
• 38: Neil Immerman, Languages that capture complexity classes, SIAM Journal on Computing, v.16 n.4, p.760-778, Aug. 1987 [doi>10.1137/0216051]
• 39: IMMERMAN, N. 1989. Descriptive and computational complexity. In Computational Complexity Theory, Proceedings of the Symposium on Applied Mathematics, vol. 38, J. Hartmanis, ed. American Mathematical Society, Providence, R.I., pp. 75-91.
• 40: IMMERMAN, N., AND LANDER, E. S. 1990. Describing graphs: A first-order approach to graph canonization. In Complexity Theory Retrospective, A. Selman, ed. Springer-Verlag, New York, pp. 59-81.
• 41: JONES, N. G., AND SELMAN, A.L. 1974. Turing machines and the spectra of first-order formulas. J. Symb. Logic 39, 139-150.
• 42: Phokion G. Kolaitis , Moshe Y. Vardi, Infinitary logics and 0–1 laws, Information and Computation, v.98 n.2, p.258-294, June 1992 [doi>10.1016/0890-5401(92)90021-7]
• 43: Phokion G. Kolaitis , Moshe Y. Vardi, On the expressive power of Datalog: tools and a case study, Journal of Computer and System Sciences, v.51 n.1, p.110-134, Aug. 1995
• 44: D. Leivant, Descriptive characterizations of computational complexity, Journal of Computer and System Sciences, v.39 n.1, p.51-83, Aug. 1989 [doi>10.1016/0022-0000(89)90019-6]
• 45: LEIVANT, D. 1989b. Monotonic use of space and computational complexity over abstract structures. Unpublished manuscript.
• 46: Daniel Leviant, Inductive definitions over finite structures, Information and Computation, v.89 n.2, p.95-108, Dec. 1990 [doi>10.1016/0890-5401(90)90006-4]
• 47: Daniel Leivant, A foundational delineation of poly-time, Papers presented at the IEEE symposium on Logic in computer science, p.391-420, May 1994, Amsterdam, The Netherlands
• 48: Steven Lindell, An analysis of fixed-point queries on binary trees, Theoretical Computer Science, v.85 n.1, p.75-95, Aug. 5, 1991 [doi>10.1016/0304-3975(91)90048-7]
• 49: LIVCHAK, A.B. 1982. The relational model for systems of automatic testing. Autom. Doc. Math. Ling. 4, 17-19.
• 50: LIVCHAK, A.B. 1983. The relational model for process control. Autom. Doc. Math. Ling. 4, 27-29.
• 51: LYNCH, J. F. 1982. Complexity classes and theories of finite models. Math. Syst. Theory 15, 127-144.
• 52: Yiannis N Moschovakis, Elementary induction on abstract structures (Studies in logic and the foundations of mathematics), American Elsevier Pub. Co, 1974
• 53: SAVITCH, W. J. 1980. Relational between nondeterministic and deterministic tape complexity. J. Comput. Syst. Sci. 4, 177-192.
• 54: Vladimir Yu. Sazonov, A Logical Approach to the Problem "P=NP?", Proceedings of the 9th Symposium on Mathematical Foundations of Computer Science, p.562-575, September 01-05, 1980
• 55: SAZONOV, V. Yu. 1980b. Polynomial computability and recursivity in finite domains. Elektron. Inf. Kybe4r. 16, 319-323.
• 56: SCHWEYTICK, T. 1994. Graph connectivity and monadic NP. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 614-622.
• 57: STOCKMEYER, L.J. 1977. The polynomial-time hierarchy. Theoret. Comput. Sci. 3, 1-22.
• 58: Howard Straubing, Finite automata, formal logic, and circuit complexity, Birkhauser Verlag, Basel, Switzerland, 1994
• 59: J. Tiuryn , P. Urzyzyn, Some relationships between logics of programs and complexity theory, Theoretical Computer Science, v.60 n.1, p.83-108, Sept., 1988 [doi>10.1016/0304-3975(88)90052-7]
• 60: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 61: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Algorithms, Theory

Keywords:
complexity classes, computational complexity, fixpoint logic, relational complexity