Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted

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).

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.