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.[1] It was originally introduced by Klaus Weihrauch in an unpublished 1992 technical report.[2]
Definition
A represented space is a pair of a set and a surjective partial function .[1]
Let be represented spaces and let be a partial multi-valued function. A realizer for is a (possibly partial) 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.[citation needed] 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:
See also
References
- ^ a b Brattka, Vasco; Gherardi, Guido; Pauly, Arno (2021), Brattka, Vasco; Hertling, Peter (eds.), "Weihrauch Complexity in Computable Analysis", Handbook of Computability and Complexity in Analysis, Cham: Springer International Publishing, pp. 367–417, doi:10.1007/978-3-030-59234-9_11, ISBN 978-3-030-59233-2, S2CID 7903709, retrieved 2022-06-29
- ^ The Degrees of Discontinuity of some Translators between Representations of the Real Numbers (Report). International Computer Science Institute. 1992.