Languages which capture complexity classes

ABSTRACT

We present in this paper a series of languages adequate for expressing exactly those properties checkable in a series of computational complexity classes. For example, we show that a graph property is in polynomial time if and only if it is expressible in the language of first order graph theory together with a least fixed point operator. As another example, a group theoretic property is in the logspace hierarchy if and only if it is expressible in the language of first order group theory together with a transitive closure operator. In this paper we also introduce a reduction between problems that is new to complexity theory. First order translations, as the name implies, are fixed first order sentences which translate one kind of structure into another. We present problems which are complete for logspace, nondeterministic logspace, polynomial time, etc., via first order translations.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: 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]
• 3: Aleliunas, Karp, Lipton, Lovasz, Rackoff, "Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems," 20th IEEE FOCS Symposium, Oct. 1979, pp. 218-223.
• 4: A.K. Chandra, D. Harel, "Structure and Complexity of Relational Queries," 21st IEEE FOCS Symposium, Oct. 1980, pp. 337-347.
• 5: 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]
• 6: H. Enderton, A Mathematical Introduction to Logic, Academic Press, 1972.
• 7: R. Fagin, "Generalized First-Order Spectra and Polynomial-Time Recognizable Sets," in Complexity of Computation, (ed. R. Karp), SIAM-AMS Proc. 7, 1974, pp. 27-41.
• 8: M. Furst, J.B. Saxe, M. Sipser, "Parity, Circuits, and the Polynomial-Time Hierarchy," 22nd IEEE FOCS Symposium, Oct. 1981, pp. 260-270.
• 9: E. Grandjean, "The Spectra of First-Order Sentences and Computational Complexity," to appear.
• 10: J. Hartmanis, N. Immerman, S. Mahaney, "One-Way Log Tape Reductions," 19th IEEE FOCS Symposium, 1978, pp. 65-72.
• 11: N. Immerman, "Number of Quantifiers is Better than Number of Tape Cells," JCSS Vol. 22, No. 3, June 1981, pp. 384-406.
• 12: Neil Immerman, Relational queries computable in polynomial time (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.147-152, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802187]
• 13: N. Immerman, "Upper and Lower Bounds for First Order Expressibility," JCSS, Vol. 25, No. 1, August, 1982.
• 14: Harry R. Lewis , Christos H. Papadimitriou, Symmetric Space-Bounded Computation (Extended Abstract), Proceedings of the 7th Colloquium on Automata, Languages and Programming, p.374-384, July 14-18, 1980
• 15: L. Lovász, P. Gács, "Some Remarks on Generalized Spectra," Zeitschr. f. math. Logik und Grundlagen d. Math, Bd. 23, pp. 547-554, 1977.
• 16: J. Lynch, "Complexity Classes and Theories of Finite Models," Math. Sys. Theory 15, 1982, pp. 127-144.
• 17: John H. Reif, Symmetric complementation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.201-214, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802193]
• 18: W. Savitch, "Maze Recognizing Automata and Nondeterministic Tape Complexity," JCSS Vol. 7, 1973, pp. 389-403.
• 19: M. Sipser, "Borel Sets and Circuit Complexity," this volume.
• 20: L. Stockmeyer, "The Polynomial-Time Hierarchy," TCS Vol. 3, 1977. pp. 1-22.
• 21: G. Turán, "On the Definability of Properties of Finite Graphs," to appear.
• 22: 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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: NATURAL

General Terms:
Languages, Theory