Spectrum of a sentence
In mathematical logic, the spectrum of a sentence is the set of natural numbers occurring as the size of a finite model in which a given sentence is true.
Definition
Let ψ be a sentence in first-order logic. The spectrum of ψ is the set of natural numbers n such that there is a finite model for ψ with n elements.
If the vocabulary for ψ consists of relational symbols, then ψ can be regarded as a sentence in existential second-order logic (ESOL) quantified over the relations, over the empty vocabulary. A generalised spectrum is the set of models of a general ESOL sentence.
Properties
Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP. It is remarkable since it is a characterization of the class NP that does not invoke a model of computation such as a Turing machine. The theorem was proven by Ronald Fagin in 1974 (strictly, in 1973 in his doctoral thesis).
As a corollary we have a result of Jones and Selman, that a set is a spectrum if and only if it is in the complexity class NEXPTIME.
See also
References
- Fagin, Ronald (1974). "Generalized First-Order Spectra and Polynomial-Time Recognizable Sets". In Karp, Richard M.. Complexity of Computation. Proc. Syp. App. Math. SIAM-AMS Proceedings 7. pp. 27–41. Zbl 0303.68035.
- Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Finite model theory and its applications. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 978-3-540-00428-8. Zbl 1133.03001.
- Immerman, Neil (1999). Descriptive Complexity. Graduate Texts in Computer Science. New York: Springer-Verlag. pp. 113–119. ISBN 0-387-98600-6. Zbl 0918.68031.
- Jones, Neil D.; Selman, Alan L. (1974). "Turing machines and the spectra of first-order formulas". J. Symb. Log. 39: 139–150. doi:10.2307/2272354. Zbl 0288.02021.