2
$\begingroup$

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.

  • 0
    @Henning: Excellent point. Indeed, i am also thinking of $\Pi_i$ as a function.2011-11-16

1 Answers 1

1

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

  • 0
    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?2011-11-17