TIME BOUNDED COMPUTATIONS OVER THE REALS

DOI10.1142/S0218196792000244MaRDI QIDQ4029500zbMATH OpenFDO

Authors Felipe Cucker, J. L. Montaña, Luis Miguel Pardo

Publication date 28 March 1993

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2117/328490

zbMATH Keywords

computations over the realsrecursionsemialgebraic sets

Mathematics Subject Classification ID

Hierarchies of computability and definability (03D55) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Symbolic computation and algebraic computation (68W30)

Review text

The paper deals with a model of computations able to work with real numbers. This model was proposed by Blum, Shub and Smale and allows inputs from an ordered ring or field. The authors here introduce the class \(TB\) of ``time bounded recursive languages: \(L \in TB\) iff there is a machine which always halts and recognizes \(L\). The definition of \(TB\) for this new model is the same as that of recursive sets in the usual (discrete) model. Nevertheless, they define different objects: the set of integers is recursive but is not in \(TB\). The authors prove that \(TB\) contains exactly those languages \(L\), each initial part \(L^{(n)}\) of which can be represented as a semialgebraic set. The rest is devoted to hierarchy results within \(TB\). These are based on the following lemma: if \(M\) is a time bounded machine and \(L\) its accepted language then \(\text{time}_ M(n)=\Omega (\log_ 2 \kappa(L^{(n)}))\) where \(\kappa(L^{(n)})\) is the number of connected components of \(l^{(n)}\). The lemma is a slight improvement of similar known result for algebraic decision trees.

Recommendations

• Recursiveness over the complex numbers is time-bounded
• A weak version of the Blum, Shub, and Smale model
• Some initial thoughts on bounded query computations over the reals
• Computing over the reals with addition and order: Higher complexity classes
• On time-space classes and their relation to the theory of real addition

Cited in

(12)

• Lower bounds for arithmetic networks
• Lower bounds for arithmetic networks. II: Sum of Betti numbers
• On the time complexity of partial real functions
• Smale's 17th problem: average polynomial time to compute affine and projective solutions
• Timed Sets, Functional Complexity, and Computability
• scientific article; zbMATH DE number 3862435 (Why is no real title available?)
• Computing in Finite Time
• Recursiveness over the complex numbers is time-bounded
• Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time
• Some initial thoughts on bounded query computations over the reals
• On genuinely time bounded computations
• On time-space classes and their relation to the theory of real addition

This page was built for publication: TIME BOUNDED COMPUTATIONS OVER THE REALS

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