On the computing power of +, -, and

DOI10.1145/2603088.2603159MaRDI QIDQ4635653zbMATH OpenOpenAlexFDO

Authors Marcello Mamino

Publication date 23 April 2018

Published in Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.4879

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Abstract: Modify the Blum-Shub-Smale model of computation replacing the permitted computational primitives (the real field operations) with any finite set $B$ of real functions semialgebraic over the rationals. Consider the class of boolean decision problems that can be solved in polynomial time in the new model by machines with no machine constants. How does this class depend on $B$? We prove that it is always contained in the class obtained for $B=+,-,imes$. Moreover, if $B$ is a set of continuous semialgebraic functions containing $+$ and $-$, and such that arbitrarily small numbers can be computed using $B$, then we have the following dichotomy: either our class is $mathsfP$ or it coincides with the class obtained for $B=+,-,imes$.

Recommendations

• Real number models under various sets of operations
• A survey on real structural complexity theory
• Computing over the reals with addition and order
• A note on a theorem of Blum, Shub, and Smale
• Computing over the reals with addition and order: Higher complexity classes

Cited in

(1)

• Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time

This page was built for publication: On the computing power of \(+\), \(-\), and \(\times\)

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