|
NeuroCOLT
Technical Report NC-TR-95-040
Descriptive Complexity
Theory over the Real Numbers
Erich
Grädel and Klaus Meer
RWTH Aachen
Germany
Abstract
We present a logical approach to complexity over the real numbers
with respect to the model of Blum, Shub and Smale. The logics under
consideration are interpreted over a special class of two-sorted structures,
called R-structures: They consist of a finite structure together
with the ordered field of reals and a finite set of functions from
the finite structure into $\R$. They are a special case of the metafinite
structures introduced recently by Gr\"adel and Gurevich.
We argue that $\R$-structures provide the right class of structures
to develop a descriptive complexity theory over $\R$. We substantiate
this claim by a number of results that relate logical definability
on $\R$-structures with complexity of computations of BSS-machines.
Download Compressed
Postscript
|