Abstract
LetL \( \subseteq \)Σ* be accepted in timef(n) by a nondeterministic Turing machine. Then there is a monadic existential second-order sentence σ in the language of + such that for everyx∈Σ*,x∈L if and only if a certain structureU f x of cardinalityf(|x|) satisfies σ. It follows that ifL is accepted in nondeterministic timen d, d a natural number, then there is a sentence whose relational symbols ared-ary or less, whose finite spectrum isL.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
G. Asser, Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität,Z. Math. Logik Grundlagen Math. 1, 252–263, 1955.
J. R. Büchi, Weak second-order arithmetic and finite automata,Z. Math. Logik Grundlagen Math. 6, 66–92, 1960.
S. A. Cook, The complexity of theorem-proving procedures,Proc. Third Annual ACM Symp. on Theory of Computing, 151–158, 1971.
S. A. Cook, A hierarchy for nondeterministic time complexity,J. Comp. Sys. Sci. 7, 343–353, 1973.
A. Ehrenfeucht, An application of games to the completeness problem for formalized theories,Fund. Math. 49, 129–141, 1961.
C. C. Elgot, Decision problems of finite-automata design and related arithmetics,Trans. AMS 98, 21–51, 1961.
R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets,Complexity of Computation, R. M. Karp, ed., AMS, Providence, 43–73, 1974.
R. Fagin, Monadic generalized spectra,Z. Math. Logic Grundlagen Math. 21, 89–96, 1975.
M. R. Garey and D. S. Johnson,Computers and Intractability, W. H. Freeman and Co., San Francisco, 1979.
J. E. Hopcroft and J. D. Ullman,Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass., 1979.
N. Immerman, Length of predicate calculus formulas as a new complexity measure,Proc. 20th Annual Symp. on Foundations of Computer Science, 337–347, 1979.
N. D. Jones and A. L. Selman, Turing machines and the spectra of first-order formulas with equality,J. Symbolic Logic 39, 139–150, 1974.
R. M. Karp, Reducibility among combinatorial problems,Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York, 85–104, 1972.
H. R. Lewis, Complexity of solvable cases of the decision problem for the predicate calculus,Proc. 19th Annual Symp. on Foundations of Computer Science, 35–47, 1978.
J. F. Lynch, Almost sure theories,Ann. Math. Logic 18, 91–135, 1980.
J. F. Lynch, On sets of relations definable by addition, to appear inJ. Symbolic Logic.
J. D. Monk,Mathematical Logic, Springer-Verlag, New York, 1976.
R. W. Ritchie, Classes of predictably computable functions,Trans. AMS 106, 139–173, 1963.
H. Scholz, Problem # 1,J. Symbolic Logic 17, 160, 1952.
L. J. Stockmeyer, The polynomial-time hierarchy,Theoretical Computer Science 3, 1–22, 1977.
Author information
Authors and Affiliations
Additional information
This research was partially supported by NSF Grants MCS78-01832 and MCS-8002695.
Rights and permissions
About this article
Cite this article
Lynch, J.F. Complexity classes and theories of finite models. Math. Systems Theory 15, 127–144 (1981). https://doi.org/10.1007/BF01786976
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01786976