Modelling the Approximation Hierarchy to Optimisation Problems Through Category Theory

Aiming at developing a theoretical framework for the formal study of NP-hard optimisation problems, we have focused on structural properties of optimisation 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 optimisation problems category OPTS and the optimisation problems category OPT, we introduce a comparison mechanism between them following the basic idea of categorical shape theory, in such way the hierarchical structure of approximation to each optimisation problem can be modelled.