Fields of Algebraic Numbers Computable in Polynomial Time. I

被引：0
|
作者：
P. E. Alaev
V. L. Selivanov
机构：
[1] Sobolev Institute of Mathematics,
[2] Novosibirsk State University,undefined
[3] ul. Pirogova 1,undefined
[4] Ershov Institute of Informatics Systems,undefined
[5] pr. Akad. Lavrent’eva 6,undefined
[6] Kazan (Volga Region) Federal University,undefined
[7] ul. Kremlevskaya 18,undefined
来源：
Algebra and Logic | 2020年 / 58卷
关键词：
field of complex algebraic numbers; ordered field of real algebraic numbers; polynomially computable presentation;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：447 / 469
页数：22
相关论文
共 50 条
  • [1] FIELDS OF ALGEBRAIC NUMBERS COMPUTABLE IN POLYNOMIAL TIME. I
    Alaev, P. E.
    Selivanov, V. L.
    ALGEBRA AND LOGIC, 2020, 58 (06) : 447 - 469
  • [2] Fields of Algebraic Numbers Computable in Polynomial Time. II
    Alaev, P. E.
    Selivanov, V. L.
    ALGEBRA AND LOGIC, 2022, 60 (06) : 349 - 359
  • [3] Fields of Algebraic Numbers Computable in Polynomial Time. II
    P. E. Alaev
    V. L. Selivanov
    Algebra and Logic, 2022, 60 : 349 - 359
  • [4] Structures Computable in Polynomial Time. I
    P. E. Alaev
    Algebra and Logic, 2017, 55 : 421 - 435
  • [5] STRUCTURES COMPUTABLE IN POLYNOMIAL TIME. I
    Alaev, P. E.
    ALGEBRA AND LOGIC, 2017, 55 (06) : 421 - 435
  • [6] Structures Computable in Polynomial Time. II
    P. E. Alaev
    Algebra and Logic, 2018, 56 : 429 - 442
  • [7] Structures Computable in Polynomial Time. II
    Alaev, P. E.
    ALGEBRA AND LOGIC, 2018, 56 (06) : 429 - 442
  • [8] Polynomial Computability of Fields of Algebraic Numbers
    P. E. Alaev
    V. L. Selivanov
    Doklady Mathematics, 2018, 98 : 341 - 343
  • [9] Polynomial Computability of Fields of Algebraic Numbers
    Alaev, P. E.
    Selivanov, V. L.
    DOKLADY MATHEMATICS, 2018, 98 (01) : 341 - 343
  • [10] The algebraic structure of the isomorphic types of tally, polynomial time computable sets
    Yongge Wang
    Archive for Mathematical Logic , 2002, 41 : 215 - 244
12345