Topological complexity of zero finding with algebraic operations

DOI10.1006/JCOM.2002.0648MaRDI QIDQ1872637zbMATH OpenOpenAlexFDO

Authors P. H. Hertling

Publication date 14 May 2003

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcom.2002.0648

zbMATH Keywords

topological complexityalgebraic operationsinformation-based complexityzero findingoracle machine overthe real numbers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Topological complexity with continuous operations
• Topological complexity of zero-finding
• scientific article; zbMATH DE number 4037051
• Can we approximate zeros of functions with nonzero topological degree?
• Some complexity results for zero finding for univariate functions

Cites work

• scientific article; zbMATH DE number 953047 (Why is no real title available?)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On decision trees for orthants
• On the topology of algorithms. I
• Randomization and the computational power of analytic and algebraic decision trees
• The real number model in numerical analysis
• Topological complexity of zero-finding
• Topological complexity with continuous operations

Cited in

(3)

• Topological complexity of zero-finding
• Stability versus speed in a computable algebraic model
• Computability on the countable ordinals and the Hausdorff-Kuratowski theorem (extended abstract)

This page was built for publication: Topological complexity of zero finding with algebraic operations

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