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.

We introduce and study certain classes of optimization problems over the real numbers. The classes are defined by logical means, relying on metafinite model theory for so called R-structures . More precisely, based on a real analogue of Fagin's theorem [12] we deal with two classes MAX-NPR and MIN-NPR of maximization and minimization problems, respectively, and figure out their intrinsic logical structure. It is proven that MAX-NPR decomposes into four natural subclasses, whereas MIN-NPR decomposes into two. This gives a real (...) number analogue of a result by Kolaitis and Thakur [13] in the Turing model. Our proofs mainly use techniques from [17]. Finally, approximation issues are briefly discussed. (shrink)

Relations between discrete and continuous complexity models are considered. The present paper is devoted to combine both models. In particular we analyze the 3-Satisfiability problem. The existence of fast decision procedures for this problem over the reals is examined based on certain conditions on the discrete setting. Moreover we study the behaviour of exponential time computations over the reals depending on the real complexity of 3-Satisfiability. This will be done using tools from complexity theory over the integers.