Abstract
Aiming at developing a theoretical framework for the formal study of NP-hard optimization problems, which is built on precise mathematical foundations, we have focused on structural properties of optimization problems related to approximative issue. From the observation that, intuitively, there are many connections among categorical concepts and structural complexity notions, in this work we present a categorical approach to cope with some questions originally studied within Computational Complexity Theory. After defining the polynomial time soluble optimization problems category OPTS and the optimization problems category OPT, a comparison mechanism between them and an approximation system to each optimization problem have been introduced, following the basic idea of categorical shape theory. In this direction, we consider new insights and a deeper understanding of some basic questions inside the Structural Complexity field, by an universal language.
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)
Barr, M., Wells, C.: Category Theory for Computing Science. Prentice Hall, New York (1990)
Cordier, J.-M., Porter, T.: Shape Theory: Categorical Approximations Methods. Ellis Horwood Ltd (1990)
Ellermann, D.P.: Category Theory and Concrete Universals. ERKENNTNIS 28(3), 409–429 (1988)
Garey, M.R., Johnson, D.S.: Computers and Intractability - A guide to the Theory of NP-Completeness. Bell Laboratories Murray Hill, New Jersey (1979)
Leal, L.A.S., Menezes, P.B., Claudio, D.M., Toscani, L.V.: Categorias dos Problemas de Otimização. In: XIV SBES - Workshop on Formal Methods - WFM2000, 3. Oct. 04–06, João Pessoa, Paraíba. Proceedings.. Brazil: SBC, p.104–109 (2000)
Leal, L.A.S., Menezes, P.B., Claudio, D.M., Toscani, L.V.: Optimization Problems Categories. In: Moreno-Díaz Jr., R., Buchberger, B., Freire, J.-L. (eds.) EUROCAST 2001. LNCS, vol. 2178, pp. 93–96. Springer, Heidelberg (2001)
Leal, L.A.S., Menezes, P.B., Claudio, D.M., Toscani, L.V.: Optimization Problems Categories. In: Moreno-Díaz Jr., R., Buchberger, B., Freire, J.-L. (eds.) EUROCAST 2001. LNCS, vol. 2178, pp. 285–299. Springer, Heidelberg (2001)
Leal, L.A.S.: Uma fundamentação Teórica para a Complexidade Estrutural de Problemas de Otimização (PhD Thesis), Universidade Federal do Rio Grande do Sul, Porto Alegre, Brazil, 115p (2002)
Leal, L.A.S., Claudio, D.M., Menezes, P.B., Toscani, L.V.: Modelling the Approximation Hierarchy to Optimisation Problems Through Category Theory. International Journal of Computing Anticipatory Systems 11, 336–349 (2002)
Papadimitriou, C.H.: Computational Complexity. Addison-Wesley Publishing Company, Reading (1994)
Rattray, C.: Identification and Recognition Through Shape in Complex Systems. In: Albrecht, R., Moreno-Díaz, R., Pichler, F. (eds.) EUROCAST 1995. LNCS, vol. 1030, pp. 19–29. Springer, Heidelberg (1995)
Rattray, C.: Abstract Modelling Complex Systems. In: Albrecht, R. (ed.) Advances in Computing Science, Systems: Theory and Practice, pp. 1–12 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
dos Santos Leal, L.A., Moraes Claudio, D., Vieira Toscani, L., Blauth Menezes, P. (2003). A Categorical Approach to NP-Hard Optimization Problems. In: Moreno-Díaz, R., Pichler, F. (eds) Computer Aided Systems Theory - EUROCAST 2003. EUROCAST 2003. Lecture Notes in Computer Science, vol 2809. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45210-2_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-45210-2_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20221-9
Online ISBN: 978-3-540-45210-2
eBook Packages: Springer Book Archive