Logics which capture complexity classes over the reals
Felipe Cucker, Klaus Meer · Journal of Symbolic Logic · 1999
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.