Polynomial Computability of Fields of Algebraic Numbers


Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

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

Supplementary Files
Action
1. JATS XML

Copyright (c) 2018 Pleiades Publishing, Ltd.