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 条

[21] FINITELY GENERATED STRUCTURES COMPUTABLE IN POLYNOMIAL TIME
Alaev, P. E.
SIBERIAN MATHEMATICAL JOURNAL, 2022, 63 (05) : 801 - 818
[22] Polynomial-time computable stable models
Palopoli, L
Zaniolo, C
ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 1996, 17 (3-4) : 261 - 290
[23] TUTTE POLYNOMIALS COMPUTABLE IN POLYNOMIAL-TIME
OXLEY, JG
WELSH, DJA
DISCRETE MATHEMATICS, 1992, 109 (1-3) : 185 - 192
[24] Atomless Boolean algebras computable in polynomial time
Alaev, Pavel Evgenievich
SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2016, 13 : 1035 - 1039
[25] Admissible closures of polynomial time computable arithmetic
Probst, Dieter
Strahm, Thomas
ARCHIVE FOR MATHEMATICAL LOGIC, 2011, 50 (5-6) : 643 - 660
[26] Polynomial-time computable stable models
Palopoli, L.
Zaniolo, C.
Annals of Mathematics and Artificial Intelligence, 17 (3-4):
[27] Parabolic Julia sets are polynomial time computable
Braverman, Mark
NONLINEARITY, 2006, 19 (06) : 1383 - 1401
[28] Finitely Generated Structures Computable in Polynomial Time
P. E. Alaev
Siberian Mathematical Journal, 2022, 63 : 801 - 818
[29] Existence and Uniqueness of Structures Computable in Polynomial Time
P. E. Alaev
Algebra and Logic, 2016, 55 : 72 - 76
[30] Cayley polynomial-time computable groups
Berdinsky, Dmitry
Elder, Murray
Kruengthomya, Prohrak
INFORMATION AND COMPUTATION, 2022, 288

← 1 2 3 4 5 →