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.