Descriptive complexity theory over the real numbers

Publisher Website
Google Scholar
Abstract
We present a logical approach to complexity over the real numbers with respect to the model of Blum, Shub and Smale. The Iogics 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 metaj%zite structures introduced recently by Gradel 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.

This publication has 0 references indexed in Scilit: