Jump to content

Weihrauch reducibility

From Wikipedia, the free encyclopedia

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

[edit]

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

[edit]

References

[edit]
  1. ^ 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, 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. ^ Weihrauch, Klaus (1992). The Degrees of Discontinuity of some Translators between Representations of the Real Numbers (Report). Informatik-Berichte. Vol. 129. FernUniversität in Hagen.