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 ${\textstyle (X,\delta )}$ of a set $X$ and a surjective partial function $\delta :\subset \mathbb {N} ^{\mathbb {N} }\rightarrow X$ .^[1]

Let $(X,\delta _{X})$ and $(Y,\delta _{Y})$ be represented spaces and let $f:\subset X\rightrightarrows Y$ be a partial multi-valued function. A realizer for $f$ is a (possibly partial) function $F:\subset \mathbb {N} ^{\mathbb {N} }\to \mathbb {N} ^{\mathbb {N} }$ such that, for every $p\in \mathrm {dom} f\circ \delta _{X}$ , $\delta _{Y}\circ F(p)=f\circ \delta _{X}(p)$ . Intuitively, a realizer $F$ for $f$ behaves "just like $f$ " but it works on names. If $F$ is a realizer for $f$ we write $F\vdash f$ .

Let $X,Y,Z,W$ be represented spaces and let $f:\subset X\rightrightarrows Y,g:\subset Z\rightrightarrows W$ be partial multi-valued functions. We say that $f$ is Weihrauch reducible to $g$ , and write $f\leq _{\mathrm {W} }g$ , if there are computable partial functions $\Phi ,\Psi :\subset \mathbb {N} ^{\mathbb {N} }\to \mathbb {N} ^{\mathbb {N} }$ such that $(\forall G\vdash g)(\Psi \langle \mathrm {id} ,G\Phi \rangle \vdash f),$ where $\Psi \langle \mathrm {id} ,G\Phi \rangle :=\langle p,q\rangle \mapsto \Psi (\langle p,G\Phi (q)\rangle )$ and $\langle \cdot \rangle$ denotes the join in the Baire space. Very often, in the literature we find $\Psi$ written as a binary function, so to avoid the use of the join.^{[citation needed]} In other words, $f\leq _{\mathrm {W} }g$ if there are two computable maps $\Phi ,\Psi$ such that the function $p\mapsto \Psi (p,q)$ is a realizer for $f$ whenever $q$ is a solution for $g(\Phi (p))$ . The maps $\Phi ,\Psi$ are often called forward and backward functional respectively.

We say that $f$ is strongly Weihrauch reducible to $g$ , and write $f\leq _{\mathrm {sW} }g$ , if the backward functional $\Psi$ does not have access to the original input. In symbols: $(\forall G\vdash g)(\Psi G\Phi \vdash f).$

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, arXiv:1707.03202, doi:10.1007/978-3-030-59234-9_11, ISBN 978-3-030-59233-2, S2CID 7903709, retrieved 2022-06-29
^ 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.

This computer science article is a stub. You can help Wikipedia by expanding it.

This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.

[:0-1] 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.

[1]

[2]

Definition

See also

References