Polynomial-time presentations of algebraic number fields

Pavel Alaev, Victor Selivanov

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-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 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
Pages20-29
Number of pages10
ISBN (Print)9783319944173
DOIs
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

Conference

Conference14th Conference on Computability in Europe, CiE 2018
CountryGermany
CityKiel
Period30.07.201803.08.2018

Keywords

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

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

Cite this