Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-23T17:55:55.907Z Has data issue: false hasContentIssue false
  • English
  • Français

Logics which capture complexity classes over the reals

Published online by Cambridge University Press:  12 March 2014

Felipe Cucker  and
Klaus Meer
Felipe Cucker
Affiliation:
Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon Tong, Hong Kong E-mail: [email protected]
Klaus Meer
Affiliation:
Lehrstuhl c Für Mathematik, Rwth Aachen, D-52056 Aachen, Germany E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 64 , Issue 1 , March 1999 , pp. 363 - 390
Copyright
Copyright © Association for Symbolic Logic 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Balcázar, J. L., Díaz, J., and Gabarró, J., Structural complexity I, EATCS Monographs on Theoretical Computer Science, vol. 11, Springer-Verlag, 1988.CrossRefGoogle Scholar
[2]J. L. Balcázar, , Díaz, J., and Gabarró, J., Structural complexity II, EATCS Monographs on Theoretical Computer Science, vol. 22, Springer-Verlag, 1990.CrossRefGoogle Scholar
[3]Blum, L., Cucker, F., Shub, M., and Smale, S., Complexity and real computation, Springer-Verlag, 1998.CrossRefGoogle Scholar
[4]Blum, L., Shub, M., and Smale, S., On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bulletin of the American Mathematical Society, vol. 21 (1989), pp. 1–46.CrossRefGoogle Scholar
[5]Borodin, A., On relating time and space to size and depth, SIAM Journal on Computing, vol. 6 (1977), pp. 733–744.CrossRefGoogle Scholar
[6]Cucker, F., Pℝ ≠ NCℝ, Journal of Complexity, vol. 8 (1992), pp. 230–238.Google Scholar
[7]Cucker, F., On the complexity of quantifier elimination: the structural approach, The Computer Journal, vol. 36 (1993), pp. 400–408.CrossRefGoogle Scholar
[8]Cucker, F. and Matamala, M., On digital nondeterminism, Mathematical Systems Theory, vol. 29 (1996), pp. 635–647.CrossRefGoogle Scholar
[9]Cucker, F. and Torrecillas, A., Two P-complete problems in the theory of the reals, Journal of Complexity, vol. 8 (1992), pp. 454–466.CrossRefGoogle Scholar
[10]Ebbinghaus, H. D. and Flum, J., Finite model theory, Springer-Verlag, 1995.Google Scholar
[11]Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, SIAM-AMS Proceedings, vol. 7 (1974), pp. 43–73.Google Scholar
[12]Grädel, E. and Gurevich, Y., Tailoring recursion for complexity, this Journal, vol. 60 (1995), pp. 952–969.Google Scholar
[13]Grädel, E. and Gurevich, Y.. Metafinite model theory, Logic and computational complexity (Leivant, D., editor), Springer-Verlag, 1996, pp. 313–366.Google Scholar
[14]Grädel, E. and Meer, K., Descriptive complexity theory over the real numbers, The mathematics of numerical analysis (Renegar, J., Shub, M., and Smale, S., editors). Lectures in Applied Mathematics, vol. 32. American Mathematical Society, 1996, pp. 381–404.Google Scholar
[15]Gross, D., Comptage sur les nombres réels, preprint. 1997.Google Scholar
[16]Immerman, N., Relational queries computable in polynomial time, Information and Control, vol. 68 (1986), pp. 86–104.CrossRefGoogle Scholar
[17]Immerman, N., Languages that capture complexity classes, SIAM Journal on Computing, vol. 16 (1987), pp. 760–778.CrossRefGoogle Scholar
[18]Meer, K., On the complexity of quadratic programming in real number models of computation, Theoretical Computer Science, vol. 133 (1994). pp. 85–94.CrossRefGoogle Scholar
[19]Meer, K., Counting problems over ℝ, Proceedings of the 22nd international symposium on mathematical foundations of computer science, bratislava. Lecture Notes in Computer Science, vol. 1295, Springer-Verlag, 1997, pp. 398–407, full paper to appear in Theoretical Computer Science.Google Scholar
[20]Meer, K. and Michaux, C., A survey on real structural complexity theory, Bulletin of the Belgian Mathematical Society, vol. 4 (1996), pp. 113–148.Google Scholar
[21]Michaux, C., Une remarque à propos à des machines sur ℝ introduites par Blum, Shub et Smale, Comptes Rendus de l’Académie des Sciences Paris, vol. 309 (1989), pp. 435–437.Google Scholar
[22]Papadimitriou, C. H., Computational complexity, Addison-Wesley, 1994.Google Scholar
[23]Renegar, J., On the computational complexity and geometry of the first-order theory of the reals. Part I, Journal of Symbolic Computation, vol. 13 (1992), pp. 255–299.Google Scholar
[24]Renegar, J., On the computational complexity and geometry of the first-order theory of the reals. Part II, Journal of Symbolic Computation, vol. 13 (1992), pp. 301–327.Google Scholar
[25]Vardi, M., Complexity of relational query languages, 14th ACM symposium on the theory of computing, 1982, pp. 137–146.Google Scholar