Weihrauch reducibility
In computable analysis, Weihrauch reducibility is a notion of reducibility between multi-valued functions on represented spaces that roughly captures the uniform computational strength of computational problems. It was originally introduced by in an unpublished 1992 technical report.
Definition
A represented space is a pair of a set and a surjective partial function.Let and be represented spaces and let be a partial multi-valued function. A realizer for is a function such that, for every,. Intuitively, a realizer for behaves "just like " but it works on names. If is a realizer for we write.
Let be represented spaces and let be partial multi-valued functions. We say that is Weihrauch reducible to, and write, if there are computable partial functions such thatwhere and denotes the join in the Baire space. Very often, in the literature we find written as a binary function, so to avoid the use of the join. In other words, if there are two computable maps such that the function is a realizer for whenever is a solution for. The maps are often called forward and backward functional respectively.
We say that is strongly Weihrauch reducible to, and write, if the backward functional does not have access to the original input. In symbols: