Logics which capture complexity classes over the reals
- 12 March 1999
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 64 (1) , 363-390
- https://doi.org/10.2307/2586770
Abstract
In this paper we deal with the logical description of complexity classes arising in the real number model of computation introduced by Blum, Shub, and Smale [4]. We adapt the approach of descriptive complexity theory for this model developped in [14] and extend it to capture some further complexity classes over the reals by logical means. Among the latter we find NCℝ, PARℝ, EXPℝ and some others more.Keywords
This publication has 15 references indexed in Scilit:
- On digital nondeterminismTheory of Computing Systems, 1996
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTOInternational Journal of Bifurcation and Chaos, 1996
- On the complexity of quadratic programming in real number models of computationTheoretical Computer Science, 1994
- On the Complexity of Quantifier Elimination: the Structural ApproachThe Computer Journal, 1993
- Two P-complete problems in the theory of the realsJournal of Complexity, 1992
- On the computational complexity and geometry of the first-order theory of the reals. Part II: The general decision problem. Preliminaries for quantifier eliminationJournal of Symbolic Computation, 1992
- On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the realsJournal of Symbolic Computation, 1992
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machinesBulletin of the American Mathematical Society, 1989
- Relational queries computable in polynomial timeInformation and Control, 1986
- On Relating Time and Space to Size and DepthSIAM Journal on Computing, 1977