Motivation. I was reading about P vs. NP and I found Cook-Levin thm, which states that any NP problem can be reduced in polynomial time to some SAT. (As I just learned, this means precisely that SAT is NP-complete (NPC))
So, let $\mathbf{NP}$ be the following category:
- objects are NP problems
- there is an arrow from $P_1$ to $P_2$ if and only if $P_1$ can be reduced in polynomial time to $P_2$ (we will denote it by $P_1\to P_2$)
Thus, from the definition of $\mathbf{NP}$, there is at most one arrow between any pair of objects (order in pair matters!).
In this language, Cook-Levin thm tells that for any problem $P$ there is an arrow from $P$ to SAT. But since there at most one such arrow, we get that SAT is a terminal object in $\mathbf{NP}$. In fact, NPCs are precisely the terminal objects in $\mathbf{NP}$.
Question. Are categories with at most one arrow between any pair of objects interesting from the perspective of category theory? Have they been studied somewhere? If so, do they have some name?
Every partially ordered or even just preordered set gives rise to a category where there is at most one arrow between any two objects. Polynomial-time reducibility is a preorder. Order theory is a sizable field on its own. It is also intimately related to category theory, because preordered sets are exactly $(0,1)$-categories, and many categorical concepts are generalizations (or categorifications) of order theoretic concepts. For example, the notion of adjunction is a generalization of the order-theoretic notion of a Galois connection.