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/

[1] P. E. Alaev, V. L. Selivanov, “Polya algebraicheskikh chisel, vychislimye za polinomialnoe vremya. I”, Algebra i logika, 58:6 (2019), 673–705 | MR

[2] P. Alaev, V. Selivanov, “Polynomial-time presentations of algebraic number fields”, Sailing routes in the world of computation, 14th conf. comput. Europe CiE 2018 (Kiel, Germany, July 30 – August 3, 2018), Lect. Notes Comput. Sci., 10936, eds. F. Manea et al., Springer, Cham, 2018, 20–29 | DOI | MR | Zbl

[3] P. E. Alaev, V. L. Selivanov, “Polinomialnaya vychislimost polei algebraicheskikh chisel”, Dokl. RAN, 481:4 (2018), 355–357 | Zbl

[4] P. E. Alaev, “Suschestvovanie i edinstvennost struktur, vychislimykh za polinomialnoe vremya”, Algebra i logika, 55:1 (2016), 106–112 | MR | Zbl

[5] P. E. Alaev, “Struktury, vychislimye za polinomialnoe vremya. I”, Algebra i logika, 55:6 (2016), 647–669 | MR

[6] D. Cenzer, J. B. Remmel, “Complexity theoretic model theory and algebra”, Handbook of recursive mathematics, v. 1, Stud. Logic Found. Math., 138, Recursive model theory, eds. Yu. L. Ershov et al., Elsevier,, Amsterdam, 1998, 381–513 | DOI | MR | Zbl

[7] A. I. Maltsev, “Konstruktivnye algebry. 1”, UMN, 16:3 (1961), 3–60 | MR | Zbl

[8] S. S. Goncharov, Yu. L. Ershov, Konstruktivnye modeli, Sibirskaya shkola algebry i logiki, Nauchnaya kniga, Novosibirsk, 1999 | MR

[9] M. Coste, M. F. Roy, “Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets”, J. Symb. Comput., 5:1/2 (1988), 121–129 | DOI | MR | Zbl

[10] Yu. L. Ershov, Teoriya numeratsii, Nauka, M., 1977 | MR

[11] P. E. Alaev, “Polinomialno vychislimye struktury s konechnym chislom porozhdayuschikh”, Algebra i logika, 59:3 (2020), 385–394 | MR | Zbl

[12] P. E. Alaev, “Konechno porozhdennye struktury, vychislimye za polinomialnoe vremya”, Sib. matem. zh. (to appear)

[13] A. Blass, Yu. Gurevich, “Equivalence relations, invariants, and normal forms”, SIAM J. Comput., 13:4 (1984), 682–689 | DOI | MR | Zbl

[14] Ch. Glasser, Ch. Reitwiessner, V. Selivanov, “The shrinking property for NP and coNP”, Theor. Comput. Sci., 412:8–10 (2011), 853–864 | DOI | MR | Zbl

[15] A. Blass, Yu. Gurevich, “Equivalence relations, invariants, and normal forms. II”, Logic and machines: decision problems and complexity, Proc. Symp. (Münster/Ger. 1983), Lect. Notes Comput. Sci., 171, 1984, 24–42 | DOI | MR | Zbl