A weak version of the Blum, Shub, and Smale model

DOI10.1006/jcss.1997.1478zbMath0869.68049OpenAlexW1986662193MaRDI QIDQ676432

Pascal Koiran

Publication date: 20 August 1997

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

Full work available at URL: https://doi.org/10.1006/jcss.1997.1478

zbMATH Keywords

Blum-Shub-Smale modelprobabilistic Turing machines

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (11)

On the computational power of dynamical systems and hybrid systems ⋮ Dynamical recognizers: real-time language recognition by analog computers ⋮ A weak version of the Blum, Shub, and Smale model ⋮ On sparseness and Turing reducibility over the reals ⋮ Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets ⋮ On a transfer theorem for the \(\text{P}\neq \text{NP}\) conjecture ⋮ On measures of space over real and complex numbers ⋮ On sparseness, reducibilities, and complexity ⋮ Exotic quantifiers, complexity classes, and complete problems ⋮ Saturation and stability in the theory of computation over the reals ⋮ Transfer theorems via sign conditions

Cites Work

• Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
• A weak version of the Blum, Shub, and Smale model
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
• Analog computation via neural networks
• Separation of complexity classes in Koiran's weak model
• Some Remarks on the Foundations of Numerical Analysis
• On the Power of Threshold Circuits with Small Weights
• Accessible telephone directories
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Bounds for the computational power and learning complexity of analog neural nets
• On the Betti Numbers of Real Varieties
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A weak version of the Blum, Shub, and Smale model