A uniform method for proving lower bounds on the computational complexity of logical theories
- 1 July 1990
- journal article
- Published by Elsevier in Annals of Pure and Applied Logic
- Vol. 48 (1) , 1-79
- https://doi.org/10.1016/0168-0072(90)90080-l
Abstract
No abstract availableKeywords
This publication has 41 references indexed in Scilit:
- Nonconvergence, undecidability, and intractability in asymptotic problemsAnnals of Pure and Applied Logic, 1987
- LOGICAL THEORIES OF ONE-PLACE FUNCTIONS ON THE SET OF NATURAL NUMBERSMathematics of the USSR-Izvestiya, 1984
- The Elementary Theory of Torsionfree Abelian Groups With a Predicate Specifying a SubgroupMathematical Logic Quarterly, 1982
- Complexity classes and theories of finite modelsTheory of Computing Systems, 1981
- Complexity results for classes of quantificational formulasJournal of Computer and System Sciences, 1980
- Separating Nondeterministic Time Complexity ClassesJournal of the ACM, 1978
- On the complexity of the theories of weak direct powersThe Journal of Symbolic Logic, 1976
- Theories of Abelian groups with predicates specifying a subgroupAlgebra and Logic, 1975
- Diophantine Problems Over Local Fields: III. Decidable FieldsAnnals of Mathematics, 1966
- ELEMENTARY THEORIESRussian Mathematical Surveys, 1965