Polynomial-time presentations of algebraic number fields

Pavel Alaev, Victor Selivanov

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

4 Citations (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.

Original languageEnglish
Title of host publicationSailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings
EditorsF Manea, RG Miller, D Nowotka
PublisherSpringer-Verlag GmbH and Co. KG
Number of pages10
ISBN (Print)9783319944173
Publication statusPublished - 1 Jan 2018
Event14th Conference on Computability in Europe, CiE 2018 - Kiel, Germany
Duration: 30 Jul 20183 Aug 2018

Publication series

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


Conference14th Conference on Computability in Europe, CiE 2018


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


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

Cite this