Geodesic
Fields of algebraic numbers computable in polynomial time. II
Algebra i logika, Tome 60 (2021) no. 6, pp. 533-548

Voir la notice de l'article provenant de la source Math-Net.Ru

This paper is a continuation of [Algebra i Logika, 58, No. 6, 673—705 (2019)], where we constructed polynomial-time presentations for the field of complex algebraic numbers and for the ordered field of real algebraic numbers. Here we discuss other known natural presentations of such structures. It is shown that all these presentations are equivalent to each other and prove a theorem which explains why this is so. While analyzing the presentations mentioned, we introduce the notion of a quotient structure. It is shown that the question whether a polynomial-time computable quotient structure is equivalent to an ordinary one is almost equivalent to the ${\rm P = NP}$ problem. Conditions are found under which the answer is positive.
Keywords: field of algebraic numbers, equivalence of polynomial-time computable structures.
Mots-clés : polynomial-time computable structures 
@article{AL_2021_60_6_a0,
     author = {P. E. Alaev and V. L. Selivanov},
     title = {Fields of algebraic numbers computable in polynomial time. {II}},
     journal = {Algebra i logika},
     pages = {533--548},
     publisher = {mathdoc},
     volume = {60},
     number = {6},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2021_60_6_a0/}
}
TY  - JOUR
AU  - P. E. Alaev
AU  - V. L. Selivanov
TI  - Fields of algebraic numbers computable in polynomial time. II
JO  - Algebra i logika
PY  - 2021
SP  - 533
EP  - 548
VL  - 60
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2021_60_6_a0/
LA  - ru
ID  - AL_2021_60_6_a0
ER  - 
%0 Journal Article
%A P. E. Alaev
%A V. L. Selivanov
%T Fields of algebraic numbers computable in polynomial time. II
%J Algebra i logika
%D 2021
%P 533-548
%V 60
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2021_60_6_a0/
%G ru
%F AL_2021_60_6_a0
P. E. Alaev; V. L. Selivanov. Fields of algebraic numbers computable in polynomial time. II. Algebra i logika, Tome 60 (2021) no. 6, pp. 533-548. http://geodesic.mathdoc.fr/item/AL_2021_60_6_a0/