# Defining Category of Problems

Let $\left\{\Pi_i\right\}_{i \in I}$ be a family of problems. Let problem $\Pi_i$ have solution $u_i$ lying in some solution space $X_i$. I am interested in making this set into a category. Is it meaningful to define morphisms between problems as follows?

Define a morphism $f_{ij}:\Pi_i \rightarrow \Pi_j$ if there exists a map $\sigma: X_i \rightarrow X_j$ such that $u_j = \sigma(u_i)$.

Any insights would be greatly appreciated.

-
You are interested in making this set into a category... for what purpose? Certainly this is a sensible definition, but whether it will actually help you do anything depends on what you want to do. –  Qiaochu Yuan Nov 16 '11 at 15:22
I want to be able to define products of problems: decomposing a bigger problem to a set of smaller ones. –  Manos Nov 16 '11 at 15:46
This sounds a bit like the category of contexts. –  Zhen Lin Nov 16 '11 at 17:56
@Zhen: this is very interesting. –  Manos Nov 16 '11 at 18:05
@Henning: I am thinking of a well-defined mathematical class of problems. For example: the matrix inversion. In that case each $\Pi_i$ would be indexed by a nonsingular matrix. –  Manos Nov 16 '11 at 21:40

## 1 Answer

Your definition as it stands seems to be too liberal to be really useful; since it only depends on one particular value of $\sigma$, you get lots of morphisms everywhere, so you won't really be capturing any notion of composing solutions.

I suspect that what you'll really want to look into is cartesian closed categories, which have a big name in theoretical computer science as models of typed lambda calculi. This will allow you to speak about composition of computable functions, et ceteral. It might be possible to define, say, a category of polynomial-time reductions using this framework (though some delicate care would be needed to avoid the full power of the lambda calculus leaking through to the problem domain).

-
Excellent hint. In fact i want my morphisms to be such that they do not depend on the particular values of the solutions. In other words, i have a general rule to maps one solution to the other. How do i express this more formally? –  Manos Nov 17 '11 at 21:53