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

DOI10.1006/JCSS.1997.1478MaRDI QIDQ676432zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3920595 (Why is no real title available?)
• scientific article; zbMATH DE number 4029737 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 16645 (Why is no real title available?)
• scientific article; zbMATH DE number 17987 (Why is no real title available?)
• scientific article; zbMATH DE number 45943 (Why is no real title available?)
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 3637287 (Why is no real title available?)
• scientific article; zbMATH DE number 3307642 (Why is no real title available?)
• A weak version of the Blum, Shub, and Smale model
• Accessible telephone directories
• Analog computation via neural networks
• Bounds for the computational power and learning complexity of analog neural nets
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the Betti Numbers of Real Varieties
• On the Power of Threshold Circuits with Small Weights
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Separation of complexity classes in Koiran's weak model
• Some Remarks on the Foundations of Numerical Analysis
• 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}\)

Cited in

(15)

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

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)