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 ℝ-structures (see [9],[8]). More precisely, based on a real analogue of Fagin’s theorem [9] we deal with two classes MAX-NP ℝ and MIN-NP ℝ of maximization and minimization problems, respectively, and figure out their intrinsic logical structure. It is proven that MAX-NP ℝ decomposes into four natural subclasses, whereas MIN-NP ℝ decomposes into two. This gives a real number analogue of a result by Kolaitis and Thakur [10] in the Turing model. Our proofs mainly use techniques from [13]. Finally, approximation issues are briefly discussed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Heidelberg (1999)
Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Springer, Heidelberg (2003)
Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, Heidelberg (1998)
Bürgisser, P., Cucker, F.: Counting Complexity Classes for Numeric Computations II: Algebraic and Semialgebraic Sets. In: Proc. 36th Symposium on Theory of Computing STOC, pp. 475–485 (2004)
Chadzelek, T., Hotz, G.: Analytic machines. Theoretical Computer Science 219, 151–167 (1999)
Cucker, F., Meer, K.: Logics which capture complexity classes over the reals. Journal of Symbolic Logic 64(1), 363–390 (1999)
Ebbinghaus, H.D., Flum, J.: Finite Model Theory. Springer, Heidelberg (1995)
Grädel, E., Gurevich, Y.: Metafinite Model Theory. In: Leivant, D. (ed.) Logic and computational complexity, pp. 313–366. Springer, Heidelberg (1996)
Grädel, E., Meer, K.: Descriptive complexity theory over the real numbers. Lectures in Applied Mathematics 32, 381–403 (1996)
Kolaitis, P.G., Thakur, M.N.: Logical definability of NP optimization problems. Information and Computation 115(2), 321–353 (1994)
Immerman, N.: Descriptive Complexity. Springer, Heidelberg (1999)
Malmström, A.: Optimization problems with approximation schemes. In: van Dalen, D., Bezem, M. (eds.) CSL 1996. LNCS, vol. 1258, pp. 316–333. Springer, Heidelberg (1997)
Meer, K.: Counting problems over the reals. Theoretical Computer Science 242, 41–58 (2000)
Meer, K.: On some relations between approximation problems and pCPs over the real numbers. In: Cooper, S.B., Löwe, B., Torenvliet, L. (eds.) CiE 2005. LNCS, vol. 3526, pp. 322–331. Springer, Heidelberg (2005)
Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation and complexity classes. Journal of Computer and System Sciences 43, 425–440 (1991)
Renegar, J.: On the computational Complexity and Geometry of the first-order Theory of the Reals, I - III. J. of Symbolic Computation 13, 255–352 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hansen, U.F., Meer, K. (2005). Two Logical Hierarchies of Optimization Problems over the Real Numbers. In: Jȩdrzejowicz, J., Szepietowski, A. (eds) Mathematical Foundations of Computer Science 2005. MFCS 2005. Lecture Notes in Computer Science, vol 3618. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11549345_40
Download citation
DOI: https://doi.org/10.1007/11549345_40
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28702-5
Online ISBN: 978-3-540-31867-5
eBook Packages: Computer ScienceComputer Science (R0)