timed set

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

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

and if aba \leq b and cdc \leq d then a+cb+da + c \leq b + d.


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

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

|x| gf=|x| f+|f(x)| g |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: