Polynomial-time presentations of algebraic number fields

Pavel Alaev, Victor Selivanov

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

4 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииSailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings
РедакторыF Manea, RG Miller, D Nowotka
ИздательSpringer-Verlag GmbH and Co. KG
Страницы20-29
Число страниц10
ISBN (печатное издание)9783319944173
DOI
СостояниеОпубликовано - 1 янв 2018
Событие14th Conference on Computability in Europe, CiE 2018 - Kiel, Германия
Продолжительность: 30 июл 20183 авг 2018

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том10936 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция14th Conference on Computability in Europe, CiE 2018
СтранаГермания
ГородKiel
Период30.07.201803.08.2018

Fingerprint Подробные сведения о темах исследования «Polynomial-time presentations of algebraic number fields». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    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-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-94418-0_2