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/

[1] E. Neumann, A. Pauly, “A topological view on algebraic computation models”, J. Complexity, 44 (2018), 1–22 | DOI | MR | Zbl

[2] A.V. Seliverstov, “Heuristic algorithms for recognition of some cubic hypersurfaces”, Program. Comput. Softw., 47:1 (2021), 50–55 | DOI | MR | Zbl

[3] A.V. Seliverstov, “Binary solutions to large systems of linear equations”, Prikl. Diskretn. Mat., 52 (2021), 5–15 | DOI | MR | Zbl

[4] L. Blum, M. Shub, S. Smale, “On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines”, Bull. Am. Math. Soc., New Ser., 21:1 (1989), 1–46 | DOI | MR | Zbl

[5] L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and real computation, Springer, New York, 1997 | MR | Zbl

[6] I.V. Ashaev, V.Ya. Belyaev, A.G. Myasnikov, “Toward a generalized computability theory”, Algebra Logic, 32:4 (1993), 183–205 | DOI | MR | Zbl

[7] A. Hemmerling, “Computability of string functions over algebraic structures”, Math. Log. Q., 44:1 (1998), 1–44 | DOI | MR | Zbl

[8] P. Koepke, A.S. Morozov, “Characterizations of ITBM-computability. I”, Algebra Logic, 59:6 (2021), 423–436 | DOI | MR | Zbl

[9] P. Koepke, A.S. Morozov, “Characterizations of ITBM-computability. II”, Algebra Logic, 60:1 (2021), 26–37 | DOI | MR | Zbl

[10] M. Carl, “Taming Koepke's zoo II: Register machines”, Ann. Pure Appl. Logic, 173:3 (2022), 103041 | DOI | MR | Zbl

[11] K. Meer, “A note on a $P \ne NP$ result for a restricted class of real machines”, J. Complexity, 8:4 (1992), 451–453 | DOI | MR | Zbl

[12] P. Koiran, “Computing over the reals with addition and order”, Theor. Comput. Sci., 133:1 (1994), 35–47 | DOI | MR | Zbl

[13] F. Cucker, M. Matamala, “On digital nondeterminism”, Math. Syst. Theory, 29:6 (1996), 635–647 | DOI | MR | Zbl

[14] C. Gaßner, “The P-DNP problem for infinite Abelian groups”, J. Complexity, 17:3 (2001), 574–583 | DOI | MR | Zbl

[15] M. Prunescu, “$P \ne NP$ for all infinite Boolean algebras”, Math. Log. Q., 49:2 (2003), 210–213 | DOI | MR | Zbl

[16] A. Rybalov, “On the $P-NP$ problem over real matrix rings”, Theor. Comput. Sci., 314:1-2 (2004), 281–285 | DOI | MR | Zbl

[17] A.N. Rybalov, “Relativizations of the $P=NP$ problem over the complex number field”, Sib. Èlectron. Mat. Izv., 1 (2004), 91–98 | MR | Zbl

[18] A. Hemmerling, “$P=NP$ for some structures over the binary words”, J. Complexity, 21:4 (2005), 557–578 | DOI | MR | Zbl

[19] C.C. Chang, H.J. Keisler, Model theory, North-Holland, Amsterdam etc, 1990 | MR | Zbl

[20] A.V. Aho, J.E. Hopcroft, J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Company, Reading, Mass. etc, 1974 | MR | Zbl

[21] P.E. Alaev, V.L. Selivanov, “Fields of algebraic numbers computable in polynomial time. I”, Algebra Logic, 58:6 (2020), 447–469 | DOI | MR | Zbl

[22] P.E. Alaev, V.L. Selivanov, “Fields of algebraic numbers computable in polynomial time. II”, Algebra Logic, 60:6 (2022), 349–359 | DOI | MR | Zbl

[23] A. Sinhababu, T. Thierauf, “Factorization of polynomials given by arithmetic branching programs”, Computat. Complexity, 30:2 (2021), 15 | DOI | MR | Zbl

[24] W. Habicht, “Eine Verallgemeinerung des Sturmschen Wurzelzählverfahrens”, Comment. Math. Helv., 21 (1948), 99–116 | DOI | MR | Zbl

[25] A.G. Akritas, Elements of computer algebra with applications, John Wiley Sons, New York etc, 1989 | MR | Zbl

[26] W.S. Brown, “The subresultant PRS algorithm”, ACM Trans. Math. Softw., 4:3 (1978), 237–249 | DOI | MR | Zbl

[27] D.D. Dzhafarov, J.R. Mileti, “The complexity of primes in computable unique factorization domains”, Notre Dame J. Formal Logic, 59:2 (2018), 139–156 | DOI | MR | Zbl

[28] K. Koiliaris, C. Xu, “Faster pseudopolynomial time algorithms for subset sum”, ACM Trans. Algorithms, 15:3 (2019), 40 | DOI | MR | Zbl

[29] A.V. Seliverstov, “On binary solutions to systems of equations”, Prikl. Diskretn. Mat., 45 (2019), 26–32 | DOI | MR | Zbl

[30] T. Alon, N. Halman, “Strongly polynomial FPTASes for monotone dynamic programs”, Algorithmica, 84:10 (2022), 2785–2819 | DOI | MR | Zbl

[31] P. Dusart, “Explicit estimates of some functions over primes”, Ramanujan J., 45:1 (2018), 227–251 | DOI | MR | Zbl