Polynomial-time presentations of algebraic number fields

Pavel Alaev; Victor Selivanov

doi:10.1007/978-3-319-94418-0_2

Polynomial-time presentations of algebraic number fields

Pavel Alaev, Victor Selivanov

Section of Algebra and Mathematical Logic

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

4 Citations (Scopus)

Abstract

Using an extension of the notion of polynomial time presentable structure we show that some natural presentations of the ordered field ℝ_alg of algebraic reals and of the field ℂ_alg of algebraic complex numbers are polynomial-time equivalent to each other and are polynomial time. We also establish upper complexity bounds for the problem of rational polynomial evaluation in ℂ_alg and for the problem of root-finding for polynomials in ℂ_alg[x] which improve the previously known bound.

Original language	English
Title of host publication	Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings
Editors	F Manea, RG Miller, D Nowotka
Publisher	Springer-Verlag GmbH and Co. KG
Pages	20-29
Number of pages	10
ISBN (Print)	9783319944173
DOIs	https://doi.org/10.1007/978-3-319-94418-0_2
Publication status	Published - 1 Jan 2018
Event	14th Conference on Computability in Europe, CiE 2018 - Kiel, Germany Duration: 30 Jul 2018 → 3 Aug 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10936 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th Conference on Computability in Europe, CiE 2018
Country	Germany
City	Kiel
Period	30.07.2018 → 03.08.2018

Keywords

Algebraic number
Complexity bound
Ordered field
Polynomial
Polynomial-time presentable structure

Access to Document

10.1007/978-3-319-94418-0_2

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Polynomial-time presentations of algebraic number fields'. Together they form a unique fingerprint.

Cite this

Alaev, P., & Selivanov, V. (2018). Polynomial-time presentations of algebraic number fields. In F. Manea, RG. Miller, & D. Nowotka (Eds.), Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings (pp. 20-29). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10936 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-94418-0_2

Alaev, Pavel ; Selivanov, Victor. / Polynomial-time presentations of algebraic number fields. Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings. editor / F Manea ; RG Miller ; D Nowotka. Springer-Verlag GmbH and Co. KG, 2018. pp. 20-29 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{86d76e5fd0d945599f407b5a8d34e6b4,

title = "Polynomial-time presentations of algebraic number fields",

abstract = "Using an extension of the notion of polynomial time presentable structure we show that some natural presentations of the ordered field ℝalg of algebraic reals and of the field ℂalg of algebraic complex numbers are polynomial-time equivalent to each other and are polynomial time. We also establish upper complexity bounds for the problem of rational polynomial evaluation in ℂalg and for the problem of root-finding for polynomials in ℂalg[x] which improve the previously known bound.",

keywords = "Algebraic number, Complexity bound, Ordered field, Polynomial, Polynomial-time presentable structure",

author = "Pavel Alaev and Victor Selivanov",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-94418-0_2",

language = "English",

isbn = "9783319944173",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag GmbH and Co. KG",

pages = "20--29",

editor = "F Manea and RG Miller and D Nowotka",

booktitle = "Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings",

address = "Germany",

note = "14th Conference on Computability in Europe, CiE 2018 ; Conference date: 30-07-2018 Through 03-08-2018",

}

Alaev, P & Selivanov, V 2018, Polynomial-time presentations of algebraic number fields. in F Manea, RG Miller & D Nowotka (eds), Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10936 LNCS, Springer-Verlag GmbH and Co. KG, pp. 20-29, 14th Conference on Computability in Europe, CiE 2018, Kiel, Germany, 30.07.2018. https://doi.org/10.1007/978-3-319-94418-0_2

Polynomial-time presentations of algebraic number fields. / Alaev, Pavel; Selivanov, Victor.

Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings. ed. / F Manea; RG Miller; D Nowotka. Springer-Verlag GmbH and Co. KG, 2018. p. 20-29 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10936 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

TY - GEN

T1 - Polynomial-time presentations of algebraic number fields

AU - Alaev, Pavel

AU - Selivanov, Victor

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Using an extension of the notion of polynomial time presentable structure we show that some natural presentations of the ordered field ℝalg of algebraic reals and of the field ℂalg of algebraic complex numbers are polynomial-time equivalent to each other and are polynomial time. We also establish upper complexity bounds for the problem of rational polynomial evaluation in ℂalg and for the problem of root-finding for polynomials in ℂalg[x] which improve the previously known bound.

AB - Using an extension of the notion of polynomial time presentable structure we show that some natural presentations of the ordered field ℝalg of algebraic reals and of the field ℂalg of algebraic complex numbers are polynomial-time equivalent to each other and are polynomial time. We also establish upper complexity bounds for the problem of rational polynomial evaluation in ℂalg and for the problem of root-finding for polynomials in ℂalg[x] which improve the previously known bound.

KW - Algebraic number

KW - Complexity bound

KW - Ordered field

KW - Polynomial

KW - Polynomial-time presentable structure

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

U2 - 10.1007/978-3-319-94418-0_2

DO - 10.1007/978-3-319-94418-0_2

M3 - Conference contribution

AN - SCOPUS:85051111244

SN - 9783319944173

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 20

EP - 29

BT - Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings

A2 - Manea, F

A2 - Miller, RG

A2 - Nowotka, D

PB - Springer-Verlag GmbH and Co. KG

T2 - 14th Conference on Computability in Europe, CiE 2018

Y2 - 30 July 2018 through 3 August 2018

ER -

Alaev P, Selivanov V. Polynomial-time presentations of algebraic number fields. In Manea F, Miller RG, Nowotka D, editors, Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings. Springer-Verlag GmbH and Co. KG. 2018. p. 20-29. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-94418-0_2