The Spectra of First-Order Sentences and Computational Complexity
- 1 May 1984
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 13 (2) , 356-373
- https://doi.org/10.1137/0213025
Abstract
No abstract availableThis publication has 11 references indexed in Scilit:
- Upper and lower bounds for first order expressibilityJournal of Computer and System Sciences, 1982
- Complexity classes and theories of finite modelsTheory of Computing Systems, 1981
- Number of quantifiers is better than number of tape cellsJournal of Computer and System Sciences, 1981
- Complexity results for classes of quantificational formulasJournal of Computer and System Sciences, 1980
- Every Prime Has a Succinct CertificateSIAM Journal on Computing, 1975
- A spectrum hierarchyMathematical Logic Quarterly, 1975
- Turing machines and the spectra of first-order formulasThe Journal of Symbolic Logic, 1974
- A hierarchy for nondeterministic time complexityJournal of Computer and System Sciences, 1973
- Quasi-realtime languagesTheory of Computing Systems, 1970
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965