nLab
timed set

Timed set

Idea

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.

Definition

Definition

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.

Definition

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

Properties

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

Examples

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

References

Timed sets were introduced in: