Standard

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. ред. / F Manea; RG Miller; D Nowotka. Springer, 2018. стр. 20-29 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10936 LNCS).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование

Harvard

Alaev, P & Selivanov, V 2018, Polynomial-time presentations of algebraic number fields. в F Manea, RG Miller & D Nowotka (ред.), 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), Том. 10936 LNCS, Springer, стр. 20-29, 14th Conference on Computability in Europe, CiE 2018, Kiel, Германия, 30.07.2018. https://doi.org/10.1007/978-3-319-94418-0_2

APA

Alaev, P., & Selivanov, V. (2018). Polynomial-time presentations of algebraic number fields. в F. Manea, RG. Miller, & D. Nowotka (Ред.), Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings (стр. 20-29). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10936 LNCS). Springer. https://doi.org/10.1007/978-3-319-94418-0_2

Vancouver

Alaev P, Selivanov V. Polynomial-time presentations of algebraic number fields. в Manea F, Miller RG, Nowotka D, Редакторы, Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings. Springer. 2018. стр. 20-29. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-94418-0_2

Author

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. Редактор / F Manea ; RG Miller ; D Nowotka. Springer, 2018. стр. 20-29 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@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",
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 = "United States",
note = "14th Conference on Computability in Europe, CiE 2018 ; Conference date: 30-07-2018 Through 03-08-2018",

}

RIS

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

UR - https://www.mendeley.com/catalogue/423a3840-5013-3ad0-a240-5b976406c79c/

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

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

Y2 - 30 July 2018 through 3 August 2018

ER -

ID: 16113332