The category of multivalued functions, with an application to many-one reductions

Arno Pauly

While multivalued functions are a natural concept in theoretical computer science, the properties of categories made up by them have been neglected - partially due to confusion with the well-studied category of relations. The talk outlines a convienient framework for categories of multivalued functions which extends p-categories as a framework for categories of partial functions.

As an application of the framework, the notion of many-one reductions between multivalued functions (sometimes called search problems here) will be formulated in category-theoretic terms. Such a formulation allows to derive basic properties of the induced degree structure without specifying the categorical setting.