Many-one reductions between search problems
Arno Pauly · arXiv (Cornell University) · 2011
Many-one reductions between search problems (i.e. multi-valued functions) play a crucial part in both algorithmic game theory (via classes such as PLS or PPAD) and the study of incomputability in analysis. While the formal setting differs significantly, the present papers offers a unifying approach in terms of category theory that allows to deduce that any degree structure arising from such reducibilities is a distributive lattice. Moreover, it is a Kleene-algebra, which allows to consider wtt-degrees, too. We discuss some specific examples and study degree-theoretic properties that do depend on the specific reducibility.