Two logical hierarchies of optimization problems over the real numbers
Uffe Flarup, Klaus Meer · Mathematical logic quarterly · 2005
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 [12, 11]). 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. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)