Feasible real random access machines

DOI10.1006/jcom.1998.0488zbMath0913.68099OpenAlexW1974032946MaRDI QIDQ1279912

Vasco Brattka, Peter H. Hertling

Publication date: 13 June 1999

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

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

zbMATH Keywords

computational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Recursive characterization of computable real-valued functions and relations ⋮ Axiomatic reals and certified efficient exact real computation ⋮ A topological view on algebraic computation models ⋮ Computational complexity of iterated maps on the interval ⋮ Effectivity and effective continuity of multifunctions ⋮ First-Order Universality for Real Programs ⋮ Arbitrary precision real arithmetic: design and algorithms ⋮ A characterization of computable analysis on unbounded domains using differential equations ⋮ Polynomial time over the reals with parsimony ⋮ The Turing closure of an Archimedean field ⋮ On approximate and algebraic computability over the real numbers ⋮ Motivations for an arbitrary precision interval arithmetic and the MPFI library ⋮ Admissibly Represented Spaces and Qcb-Spaces ⋮ Stability versus speed in a computable algebraic model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quasi-gcd computations
• On the complexity of online computations of real functions
• \(\delta\)-uniform BSS machines
• The real number model in numerical analysis
• Recursive characterization of computable real-valued functions and relations
• Type 2 computational complexity of functions on Cantor's space
• On the definitions of computable real continuous functions
• Fast Multiple-Precision Evaluation of Elementary Functions
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Fast online multiplication of real numbers