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 that

where 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:

See also

References

  1. 1 2 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, arXiv:1707.03202, doi:10.1007/978-3-030-59234-9_11, ISBN 978-3-030-59233-2, S2CID 7903709, retrieved 2022-06-29
  2. The Degrees of Discontinuity of some Translators between Representations of the Real Numbers (Report). International Computer Science Institute. 1992.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.