Fields of algebraic numbers computable in polynomial time. II. (English. Russian original) Zbl 1515.03158
Algebra Logic 60, No. 6, 349-359 (2022); translation from Algebra Logika 60, No. 6, 533-548 (2021).
Summary: This paper is a continuation of [Algebra Logic 58, No. 6, 447–469 (2020; Zbl 1484.03058); translation from Algebra 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 \(\mathrm{P} = \mathrm{NP}\) problem. Conditions are found under which the answer is positive.
MSC:
| 03C57 | Computable structure theory, computable model theory |
| 03D45 | Theory of numerations, effectively presented structures |
| 11R04 | Algebraic numbers; rings of algebraic integers |
| 11Y16 | Number-theoretic algorithms; complexity |
| 11U09 | Model theory (number-theoretic aspects) |
Keywords:
field of algebraic numbers; polynomial-time computable structures; equivalence of polynomial-time computable structuresCitations:
Zbl 1484.03058References:
| [1] | Alaev, PE; Selivanov, VL, Fields of algebraic numbers computable in polynomial time. I, Algebra and Logic, 58, 6, 447-469 (2019) · Zbl 1484.03058 · doi:10.1007/s10469-020-09565-0 |
| [2] | Alaev, PE; Selivanov, VL, Polynomial-time presentations of algebraic number fields, Lect. Notes Comput. Sci., 10936, 20-29 (2018) · Zbl 1509.03107 · doi:10.1007/978-3-319-94418-0_2 |
| [3] | Alaev, PE; Selivanov, VL, Polynomial computability of algebraic number fields, Dokl. RAN, 481, 4, 355-357 (2018) · Zbl 1509.03107 |
| [4] | Alaev, PE, Existence and uniqueness of structures computable in polynomial time, Algebra and Logic, 55, 1, 72-76 (2016) · Zbl 1361.03042 · doi:10.1007/s10469-016-9377-6 |
| [5] | Alaev, PE, Structures computable in polynomial time. I, Algebra and Logic, 55, 6, 421-435 (2016) · Zbl 1420.03104 · doi:10.1007/s10469-017-9416-y |
| [6] | D. Cenzer and J. B. Remmel, “Complexity theoretic model theory and algebra,” in Handbook of Recursive Mathematics, Vol. 1, Recursive Model Theory, Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel (Eds.), Stud. Log. Found. Math., 138, Elsevier, Amsterdam (1998), pp. 381-513. · Zbl 0941.03035 |
| [7] | A. I. Mal’tsev, “Constructive algebras. I,” Usp. Mat. Nauk, 16, No. 3, 3-60 (1961). · Zbl 0129.25903 |
| [8] | Goncharov, SS; Ershov, YL, Constructive Models, Siberian School of Algebra and Logic (1999), Novosibirsk: Nauch. Kniga, Novosibirsk · Zbl 1043.03518 |
| [9] | M. Coste M. and 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, Nos. 1/2, 121-129 (1988). · Zbl 0689.14006 |
| [10] | Ershov, YL, Numeration Theory (1977), Moscow: Nauka, Moscow |
| [11] | Alaev, PE, Polynomially computable structures with finitely many generators, Algebra and Logic, 59, 3, 266-272 (2020) · Zbl 1484.03079 · doi:10.1007/s10469-020-09598-5 |
| [12] | P. E. Alaev, “Finitely generated structures computable in polynomial time,” submitted to Sib. Math. J. · Zbl 1420.03105 |
| [13] | Blass, A.; Gurevich, Y., Equivalence relations, invariants, and normal forms, SIAM J. Comput., 13, 4, 682-689 (1984) · Zbl 0545.68035 · doi:10.1137/0213042 |
| [14] | Glasser, C.; Reitwiessner, C.; Selivanov, V., The shrinking property for NP and coNP, Theor. Comput. Sci., 412, 8-10, 853-864 (2011) · Zbl 1223.68040 · doi:10.1016/j.tcs.2010.11.035 |
| [15] | A. Blass and Y. Gurevich, “Equivalence relations, invariants, and normal forms. II,” in Logic and Machines: Decision Problems and Complexity, Lect. Notes Comp. Sci., 171, Springer, Berlin (1984), pp. 24-42. · Zbl 0545.68036 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
