The problems of decidability (and the decidability complexity) of the theories in some signatures with different supports are considered. The solvability by an algorithm from the class EXPTIME of the universal positive theory of the signature ⟨ ̅Q₀;|Pol_Q0,max,min,≤ ⟩, in which the coefficients and degree of polynomials are written in binary number system is proved. In addition, the decidability of the universal positive theory of rings of all k-ary rational numbers, greater than a given constant, and all k-ary rational numbers, not greater than a given constant, is proved. The NP-hardness of all these problems is proved. The algorithmic undecidability of universal theories of rings of all k-ary rational numbers as k ≥ 2. The latter problem can be considered as a computer-oriented modification of the problem of solvability of the universal field theory of rational numbers.

algorithmic decidability, computational complexity, universal theories of rational numbers

Mathematical problems and theory of numerical methods