Geodesic
The recognition complexity of decidable theories
Eurasian mathematical journal, Tome 13 (2022) no. 1, pp. 44-68.

Voir la notice de l'article provenant de la source Math-Net.Ru

We will find a lower bound on the recognition complexity of the decidable theories that are nontrivial relative to equality, namely, each of these theories is consistent with the formula, whose sense is that there exist at least two distinct elements. However, at first, we will obtain a lower bound on the computational complexity for the first-order theory of the Boolean algebra that contains only two elements. For this purpose, we will code the long-continued deterministic Turing machine computations by the relatively short-length quantified Boolean formulae; the modified Stockmeyer and Meyer method will appreciably be used for this simulation. Then, we will construct a polynomial reduction of this theory to the first-order theory of pure equality. 
@article{EMJ_2022_13_1_a4,
     author = {I. V. Latkin},
     title = {The recognition complexity of decidable theories},
     journal = {Eurasian mathematical journal},
     pages = {44--68},
     publisher = {mathdoc},
     volume = {13},
     number = {1},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/EMJ_2022_13_1_a4/}
}
TY  - JOUR
AU  - I. V. Latkin
TI  - The recognition complexity of decidable theories
JO  - Eurasian mathematical journal
PY  - 2022
SP  - 44
EP  - 68
VL  - 13
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/EMJ_2022_13_1_a4/
LA  - en
ID  - EMJ_2022_13_1_a4
ER  - 
%0 Journal Article
%A I. V. Latkin
%T The recognition complexity of decidable theories
%J Eurasian mathematical journal
%D 2022
%P 44-68
%V 13
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/EMJ_2022_13_1_a4/
%G en
%F EMJ_2022_13_1_a4
I. V. Latkin. The recognition complexity of decidable theories. Eurasian mathematical journal, Tome 13 (2022) no. 1, pp. 44-68. http://geodesic.mathdoc.fr/item/EMJ_2022_13_1_a4/

[1] A. V. Aho, J. E. Hopcroft, J. D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Company, Reading, Massachusetts, 1976

[2] S. Arora, B. Barak, Computational complexity: a modern approach, Cambridge University Press, 2009

[3] G. Baumslag, D. Gildenhuys, R. Strebel, “Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras I”, J. Pure and Applied Algebra, 39:1-2 (1986), 53–94

[4] K. J. Compton, C. W. Henson, “A uniform method for proving lower bounds on the computational complexity of logical theories”, Ann. Pure Appl. Logic, 48:1 (1990), 1–79

[5] S. A. Cook, “The complexity of theorem-proving procedures”, Proc. of the 3$^{rd}$ Annual ACM Symposium on the Theory of Computing (Shaker Heights, Ohio, 1971), 151–159

[6] Y. L. Ershov, I. A. Lavrov, A. D. Taimanov, M. A. Taitslin, “Elementary theories”, Russian Math. Surveys, 20 (1965), 35–100 (English translation)

[7] M. J. Fisher, M. O. Rabin, “Super exponential complexity of Presburger's arithmetic”, AMS Proceedings, 7, SIAM, 1974, 27–41

[8] K. Fleischmann, B. Mahr, D. Siefkes, “Bounded concatenation theory as a uniform method for proving lower complexity bounds”, Logic Colloquium, 76, eds. R. Gandy, M. Hyland, North-Holland, Amsterdam, 1977, 471–490

[9] M. R. Garey, D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness, Freeman, New York, 1979

[10] B. Sh. Kulpeshov, S. V. Sudoplatov, “Distributions of countable models of quite o-minimal Ehrenfeucht theories”, Eurasian Math. J., 11:3 (2020), 66–78

[11] I. V. Latkin, “The occurrence problem for subvarieties of the variety N$_2$A, revisited”, Algebra and Logic, 40:5 (2001), 327–333

[12] A. I. Malcev, Algorithms and recursive functions, Wolters-Noordhoff Pub. Co., 1970

[13] N. D. Markhabatov, S. V. Sudoplatov, “Ranks for families of all theories of given languages”, Eurasian Math. J., 12:2 (2021), 52–58

[14] A. R. Meyer, Weak monadic second order theory of successor is not elementary-recursive, Technical Report (Memo 38), Massachusetts Institute of Technology, Cambridge, MA, USA, 1973

[15] A. R. Meyer, “The inherent complexity of the theories of ordered sets”, International Congress of Mathematians (Vancouver, 1974); Canadian Math. Congress, 1975, 477–482

[16] A. R. Meyer, L. J. Stockmeyer, “The equivalence problem for regular expressions with squaring requires exponetial space”, Proc. Thirteenth Annual IEEE Symposium on Switching and Automata theory, 1972, 125–129

[17] M. O. Rabin, “Decidable theories”, Handbook of mathematical logic, Part C, Chapter 3, eds. J. Barwise, Elsevier, Amsterdam–New York; Eighth impression, 1999, 596–629

[18] E. L. Robertson, Structure of complexity in the weakmonadic second-order theories of the natural numbers, Research Report CS-73-31, Dept. of Applied Analysis and Computer Science, University of Waterloo, Dec. 1973; Proc. 6th ACM Symp. on Theory of Computing, 1974, 161–171

[19] L. J. Stockmeyer, The complexity of decision problems in automata theory and logic, PhD thesis, MIT Lab for Computer Science, 1974; /MIT/LCS TechRep 133

[20] L. J. Stockmeyer, A. R. Meyer, “Word problems requiring exponential time”, Proc. 5th Ann. ACM Symp. on the Theory of Computing, Association for Computing Machinery, New York, 1973, 1–9

[21] S. Vorobyov, “The most nonelementary theory”, Information and Computation, 190:2 (2004), 196–219