Abstract

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