Citation
F. Cucker et K. Meer, Logics which capture complexity classes over the reals, J SYMB LOG, 64(1), 1999, pp. 363-390
Citations number
25
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF SYMBOLIC LOGIC
ISSN journal
00224812
→ ACNP
Volume
64
Issue
1
Year of publication
1999
Pages
363 - 390
Database
ISI
SICI code
0022-4812(199903)64:1<363:LWCCCO>2.0.ZU;2-X
Abstract
In this paper we deal with the logical description of complexity classes ar
ising 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 NCR, PAR(
R), EXPR and some others more.