Geodesic
On computations over ordered rings
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 1054-1076

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

We consider generalized register machines over ordered rings with an auxiliary binary operation. In particular, we consider the ring of integers, its infinite Cartesian power, and ultrapowers. The feasibility and computational complexity of some algorithms are discussed. There is also given an example of a non-factorial ring, which is elementarily equivalent to the ring of integers. It is shown that non-deterministic computations with integers can be implemented as computations over the Cartesian power of the ring of integers. It is also possible to model calculations with an oracle using such machines. This provides an algebraic approach to describing some classes of computational complexity. However, this model of computation differs significantly from alternating machines. Moreover, various types of non-deterministic machines are considered.
Keywords: generalized register machine, ring, integral domain, integers, ultrapower, non-deterministic computations
Mots-clés : polynomial time, oracle. 
@article{SEMR_2022_19_2_a14,
     author = {I. V. Latkin and A. V. Seliverstov},
     title = {On computations over ordered rings},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1054--1076},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a14/}
}
TY  - JOUR
AU  - I. V. Latkin
AU  - A. V. Seliverstov
TI  - On computations over ordered rings
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2022
SP  - 1054
EP  - 1076
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a14/
LA  - ru
ID  - SEMR_2022_19_2_a14
ER  - 
%0 Journal Article
%A I. V. Latkin
%A A. V. Seliverstov
%T On computations over ordered rings
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2022
%P 1054-1076
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a14/
%G ru
%F SEMR_2022_19_2_a14
I. V. Latkin; A. V. Seliverstov. On computations over ordered rings. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 1054-1076. http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a14/