Polynomial Computability of Fields of Algebraic Numbers
- Authors: Alaev P.E.1,2, Selivanov V.L.3,4
-
Affiliations:
- Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences
- Novosibirsk State University
- Ershov Institute of Informatics System of the Siberian Branch of the Russian Academy of Sciences
- Kazan Federal University
- Issue: Vol 98, No 1 (2018)
- Pages: 341-343
- Section: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/225529
- DOI: https://doi.org/10.1134/S1064562418050137
- ID: 225529
Cite item
Abstract
We prove that the field of complex algebraic numbers and the ordered field of real algebraic numbers have isomorphic presentations computable in polynomial time. For these presentations, new algorithms are found for evaluation of polynomials and solving equations of one unknown. It is proved that all best known presentations for these fields produce polynomially computable structures or quotient-structures such that there exists an isomorphism between them polynomially computable in both directions.
About the authors
P. E. Alaev
Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences; Novosibirsk State University
Author for correspondence.
Email: alaev@math.nsc.ru
Russian Federation, Novosibirsk, 630090; Novosibirsk, 630090
V. L. Selivanov
Ershov Institute of Informatics System of the Siberian Branch of the Russian Academy of Sciences; Kazan Federal University
Email: alaev@math.nsc.ru
Russian Federation, Novosibirsk; Kazan, Republic of Tatarstan, 420008
Supplementary files
