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/