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 (see [9], [8]). More precisely, based on a real analogue of Fagin's theorem [9] we deal with two classes MAX-N P_R and MIN-N P_R of maximization and minimization problems, respectively, and figure out their intrinsic logical structure. It is proven that MAX-N P_R decomposes into four natural subclasses, whereas MIN-N P_R decomposes into two. This gives a real number analogue of a result by Kolaitis and Thakur in the Turing model. Our proofs mainly use techniques from. Finally, approximation issues are briefly discussed.
展开▼
