timed set

Some functions are more expensive to calculate than others. Additionally, calculation with large values is more expensive than with small values. A category of timed sets has additional structure which measures the cost of computation for each function.

When properly qualified and constructed, categories of timed sets can provide categorical descriptions of complexity classes.

A size monoid is a commutative monoid with a partial order $\leq$ such that

$\underset{m \in M}{\forall} \;\; 0 \leq m$

and if $a \leq b$ and $c \leq d$ then $a + c \leq b + d$.

For a size monoid $M$, a timed map $f$ is a partial function $X \to Y$ and a partial cost function called the timing, $|-|_f : X \to M$ which are defined on the same elements of $X$.

Given a size monoid $M$, there is a category $\mathtt{TSet}(M)$ of sets and $M$-timed maps. The identity morphism has the zero function for timing. The composition of the cost of two morphisms $f : X \to Y$ and $g : Y \to Z$ is given by

$|x|_{g \circ f} = |x|_f + |f(x)|_g$

As categories of sets and partial functions, categories of timed sets are restriction categories.

The complexity classes PTIME? and LOGSPACE? can be described by categories of timed sets.

Timed sets were introduced in:

- Robin Cockett, Joaquín Díaz-Boils?, Jonathan Gallagher?, Pavel Hrubeŝ?,
*Timed Sets, Functional Complexity, and Computability*, Electronic Notes in Theoretical Computer Science, volume 286, 2012 (doi:10.1016/j.entcs.2012.08.009)