THE RECOGNITION COMPLEXITY OF DECIDABLE THEORIES
Latkin I.V.
2022L.N. Gumilyov Eurasian National University
Eurasian Mathematical Journal
2022#13Issue 144 - 68 pp.
We will nd 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 rst, we will obtain a lower bound on the computational complexity for the rst-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 quanti ed Boolean formulae; the modi ed Stockmeyer and Meyer method will appreciably be used for this simulation. Then, we will construct a polynomial reduction of this theory to the rst-order theory of pure equality.
Decidable theories , lower complexity bound , polynomial space , polynomial time , the coding of computations , the theory of equality
Text of the article Перейти на текст статьи
Faculty of Basic Engineering Training, D. Serikbayev East Kazakhstan Technical University, 69 Protozanov St., Ust-Kamenogorsk, 070004, Kazakhstan
Faculty of Basic Engineering Training
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026