Satisfiability of cross product terms is complete for real nondeterministic polytime Blum-Shub-Smale machines

MaRDI QIDQ4992873zbMATH OpenFDO

Authors Christian Herrmann, Johanna Sokoli, Martin Ziegler

Publication date 10 June 2021

Full work available at URL https://arxiv.org/abs/1309.1270, http://eptcs.web.cse.unsw.edu.au/paper.cgi?MCU2013.16

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78) Other nonclassical models of computation (68Q09) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On NP-completeness for linear machines
• A note on a theorem of Blum, Shub, and Smale
• \(\text{P}\neq \text{NP}\) for the reals with various analytic functions
• On the Structure of $\cal NP_\Bbb C$
• Topics in real and complex number complexity theory

Cited in

(1)

• Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations

This page was built for publication: Satisfiability of cross product terms is complete for real nondeterministic polytime Blum-Shub-Smale machines

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