Fields of Algebraic Numbers Computable in Polynomial Time. II

Standard

Fields of Algebraic Numbers Computable in Polynomial Time. II. / Alaev, P. E.; Selivanov, V. L.

In: Algebra and Logic, Vol. 60, No. 6, 01.01.2022, p. 349-359.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{d8bba6157e1b4f5b8faa30027ce5aa3b,

title = "Fields of Algebraic Numbers Computable in Polynomial Time. II",

abstract = "This paper is a continuation of [Algebra and Logic, 58, No. 6, 447-469 (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 P = NP problem. Conditions are found under which the answer is positive.",

keywords = "equivalence of polynomial-time computable structures, field of algebraic numbers, polynomial-time computable structures",

author = "Alaev, {P. E.} and Selivanov, {V. L.}",

year = "2022",

month = jan,

day = "1",

doi = "10.1007/s10469-022-09661-3",

language = "English",

volume = "60",

pages = "349--359",

journal = "Algebra and Logic",

issn = "0002-5232",

publisher = "Springer Nature",

number = "6",

}

RIS

TY - JOUR

T1 - Fields of Algebraic Numbers Computable in Polynomial Time. II

AU - Alaev, P. E.

AU - Selivanov, V. L.

PY - 2022/1/1

Y1 - 2022/1/1

N2 - This paper is a continuation of [Algebra and Logic, 58, No. 6, 447-469 (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 P = NP problem. Conditions are found under which the answer is positive.

AB - This paper is a continuation of [Algebra and Logic, 58, No. 6, 447-469 (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 P = NP problem. Conditions are found under which the answer is positive.

KW - equivalence of polynomial-time computable structures

KW - field of algebraic numbers

KW - polynomial-time computable structures

UR - http://www.scopus.com/inward/record.url?scp=85129422870&partnerID=8YFLogxK

U2 - 10.1007/s10469-022-09661-3

DO - 10.1007/s10469-022-09661-3

M3 - Article

AN - SCOPUS:85129422870

VL - 60

SP - 349

EP - 359

JO - Algebra and Logic

JF - Algebra and Logic

SN - 0002-5232

IS - 6

ER -

ID: 126984768