Two logical hierarchies of optimization problems over the real numbers
✍ Scribed by Uffe Flarup; Klaus Meer
- Publisher
- John Wiley and Sons
- Year
- 2006
- Tongue
- English
- Weight
- 209 KB
- Volume
- 52
- Category
- Article
- ISSN
- 0044-3050
No coin nor oath required. For personal study only.
✦ Synopsis
Dedicated to Professor Günter Asser on the occasion of his eightieth birthday
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-NP R and MIN-NP R of maximization and minimization problems, respectively, and figure out their intrinsic logical structure. It is proven that MAX-NP R decomposes into four natural subclasses, whereas MIN-NP R 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.