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

DOI10.1006/JCSS.1997.1478zbMATH Open0869.68049OpenAlexW1986662193MaRDI QIDQ676432FDOQ676432

Authors: 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

Recommendations

• On weak and weighted computations over the real closure of \(\mathbb{Q}\)
• A survey on real structural complexity theory
• Computing over the reals with addition and order

zbMATH Keywords

probabilistic Turing machinesBlum-Shub-Smale model

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (15)

• Transfer theorems via sign conditions
• A variation on Smilansky's model
• On sparseness and Turing reducibility over the reals
• Three inadequate models
• TIME BOUNDED COMPUTATIONS OVER THE REALS
• On the computational power of dynamical systems and hybrid systems
• On measures of space over real and complex numbers
• Exotic quantifiers, complexity classes, and complete problems
• Saturation and stability in the theory of computation over the reals
• On sparseness, reducibilities, and complexity
• Dynamical recognizers: real-time language recognition by analog computers
• On a transfer theorem for the \(\text{P}\neq \text{NP}\) conjecture
• On weak and weighted computations over the real closure of \(\mathbb{Q}\)
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
• A weak version of the Blum, Shub, and Smale model

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

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