It is proved that the field of complex algebraic numbers has an isomorphic presentation computable in polynomial time. A similar fact is proved for the ordered field of real algebraic numbers. The constructed polynomially computable presentations are based on a natural presentation of algebraic numbers by rational polynomials. Also new algorithms for computing values of polynomials on algebraic numbers and for solving equations in one variable with algebraic coefficients are presented.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D. Cenzer and J. B. Remmel, “Complexity theoretic model theory and algebra,” in Handbook of Recursive Mathematics, Vol. 1, Recursive Model Theory, Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel (Eds.), Stud. Log. Found. Math., 138, Elsevier, Amsterdam (1998), pp. 381-513.
G. E. Collins and R. Loos, “Real zeroes of polynomials,” in Computer Algebra. Symbolic and Algebraic Computations, Comput. Suppl., 4, Springer-Verlag, New York (1982), pp. 83-94.
R. Loos, “Computing in algebraic extensions,” in Computer Algebra: Symbolic and Algebraic Computations, Comput. Suppl., 4, Springer-Verlag, New York (1982), 173-187.
A. K. Lenstra, H. W. Lenstra, and L. Lovász, “Factoring polynomials with rational coefficients,” Math. Ann., 261, 515-534 (1982).
M. O. Rabin, “Computable algebra, general theory and theory of computable fields,” Trans. Am. Math. Soc., 95, 341-360 (1960).
Yu. L. Eršov, “Theorie der Numerierungen. III,” Z. Math. Logik Grundl. Math., 23, No. 4, 289-371 (1977).
S. S. Goncharov and Yu. L. Ershov, Constructive Models, Sib. School Alg. Log. [in Russian], Nauch. Kniga, Novosibirsk (1999).
G. E. Collins, “The calculation of multivariate polynomial resultants,” J. Assoc. Comput. Mach., 18, No. 4, 515-532 (1971).
F. Winkler, Polynomial Algorithms in Computer Algebra, Texts Monogr. Symb. Comput., Springer, Wien (1996).
H. Cohen, A Course in Computational Algebraic Number Theory, Grad. Texts Math., 138, Springer-Verlag, Berlin (1993).
C. K. Yap, Fundamental Problems of Algorithmic Algebra, Oxford Univ. Press, Oxford (2000).
G. E. Collins, “Quantifier elimination for real closed fields by cylindrical decomposition,” in Lect. Notes Comput. Sci., 33 (1975), pp. 134-183.
P. E. Alaev, “Existence and uniqueness of structures computable in polynomial time,” Algebra and Logic, 55, No. 1, 72-76 (2016).
P. E. Alaev, “Structures computable in polynomial time. I,” Algebra and Logic, 55, No. 6, 421-435 (2016).
A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA (1974).
A. Akritas, Elements of Computer Algebra with Applications, Wiley (1989).
A. Schrijver, Theory of Linear and Integer Programming, Wiley (1998).
Jianping Zhou, “On the degree of extensions generated by finitely many algebraic numbers,” J. Number Th., 34, No. 2, 133-141 (1990).
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by RFBR (project No. 17-01-00247) and by the RF Ministry of Science and Higher Education (state assignment to Sobolev Institute of Mathematics, SB RAS, project No. 0314-2019-0002).
The work was carried out at the expense of the subsidy allocated to Kazan (Volga Region) Federal University for the fulfillment of the state assignment in the sphere of scientific activity, project No. 1.13556.2019/13.1.
Translated from Algebra i Logika, Vol. 58, No. 6, pp. 673-705, November-December, 2019.
Rights and permissions
About this article
Cite this article
Alaev, P.E., Selivanov, V.L. Fields of Algebraic Numbers Computable in Polynomial Time. I. Algebra Logic 58, 447–469 (2020). https://doi.org/10.1007/s10469-020-09565-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10469-020-09565-0