A note on a theorem of Blum, Shub, and Smale

DOI10.1016/0885-064X(90)90004-WMaRDI QIDQ909656zbMATH OpenDBLPWikidataFDO

Authors Eberhard Triesch

Publication date 1990

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

Full work available at URL https://doi.org/10.1016/0885-064X(90)90004-W

zbMATH Keywords

computations over the real numbersNP-completeness over \({\mathbb{R}}\)polynomial-time solvability of the k-Feasibility-Problem for k\(\leq 3\)

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Topics in real and complex number complexity theory
• A survey on real structural complexity theory
• Real number computations: On the use of information
• The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete.

Cited in

(10)

• Computational complexity over the \(p\)-adic numbers
• Real data-integer solution problems within the Blum-Shub-Smale computational model
• Real computations with fake numbers
• The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete.
• Complexity and dimension
• scientific article; zbMATH DE number 503394 (Why is no real title available?)
• On the computing power of +, -, and
• Satisfiability of cross product terms is complete for real nondeterministic polytime Blum-Shub-Smale machines
• Fixed points, Nash equilibria, and the existential theory of the reals
• Computations over \(\mathbb{Z}\) and \(\mathbb{R}\): a comparison

This page was built for publication: A note on a theorem of Blum, Shub, and Smale

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