Correction to ``Computational complexity of algebraic functions

DOI10.1016/0022-0000(88)90015-3MaRDI QIDQ1109564zbMATH OpenOpenAlexFDO

Authors Nicholas Pippenger

Publication date 1988

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(88)90015-3

zbMATH Keywords

cost of root extractionradical complexityrational function of rootsstraight line programs

Mathematics Subject Classification ID

Algebraic numbers; rings of algebraic integers (11R04) Analysis of algorithms and problem complexity (68Q25)

Review text

In the author's paper [(*)\ ibid. 22, 454-470 (1981; Zbl 0469.68045)], the proof of Proposition 5.2 is erroneous. Specifically, the assertion immediately preceding the proposition is false, and the proof of the proposition given in (*) relies on this assertion. The object of this note is to give a correct proof of Proposition 5.2 of (*).

Recommendations

• Corrigendum to: ``On the decidability of semilinearity for semialgebraic sets and its implications for spatial databases
• Corrigendum to: ``On the field of definition of a cubic rational function and its critical points.
• Errata to: The algebra of slice functions
• Correction to: Depth functions of symbolic powers of homogeneous ideals
• Erratum: Factoring Polynomials over Algebraic Number Fields

Cites work

• Computational complexity of algebraic functions

Cited in

(5)

• Corrigendum to: ``On the decidability of semilinearity for semialgebraic sets and its implications for spatial databases
• Correction to: ``Tropical varieties for exponential sums
• Comments on ``Arithmetic complexity, Kleene closure, and formal power series
• scientific article; zbMATH DE number 4066342 (Why is no real title available?)
• Errata to: The algebra of slice functions

This page was built for publication: Correction to ``Computational complexity of algebraic functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1109564)