Logics which capture complexity classes over the reals

Journal of Symbolic Logic 64 (1):363-390 (1999)
  Copy   BIBTEX


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 R , PAR R , EXP R and some others more



    Upload a copy of this work     Papers currently archived: 94,623

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Accessible telephone directories.John B. Goode - 1994 - Journal of Symbolic Logic 59 (1):92-105.
On the Relations Between Discrete and Continuous Complexity Theory.Klaus Meer - 1995 - Mathematical Logic Quarterly 41 (2):281-286.


Added to PP

23 (#687,158)

6 months
13 (#282,653)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Finite Model Theory.Heinz-Dieter Ebbinghaus & Torg Flum - 1997 - Studia Logica 58 (2):332-335.

Add more references