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

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

Let ${\displaystyle X,Y,Z,W}$  be represented spaces and let ${\displaystyle f:\subset X\rightrightarrows Y,g:\subset Z\rightrightarrows W}$  be partial multi-valued functions. We say that ${\displaystyle f}$  is Weihrauch reducible to ${\displaystyle g}$ , and write ${\displaystyle f\leq _{\mathrm {W} }g}$ , if there are computable partial functions ${\displaystyle \Phi ,\Psi :\subset \mathbb {N} ^{\mathbb {N} }\to \mathbb {N} ^{\mathbb {N} }}$  such that

$${\displaystyle (\forall G\vdash g)(\Psi \langle \mathrm {id} ,G\Phi \rangle \vdash f),}$$

 

where ${\displaystyle \Psi \langle \mathrm {id} ,G\Phi \rangle :=\langle p,q\rangle \mapsto \Psi (\langle p,G\Phi (q)\rangle )}$  and ${\displaystyle \langle \cdot \rangle }$  denotes the join in the Baire space. Very often, in the literature we find ${\displaystyle \Psi }$  written as a binary function, so to avoid the use of the join.^{[citation needed]} In other words, ${\displaystyle f\leq _{\mathrm {W} }g}$  if there are two computable maps ${\displaystyle \Phi ,\Psi }$  such that the function ${\displaystyle p\mapsto \Psi (p,q)}$  is a realizer for ${\displaystyle f}$  whenever ${\displaystyle q}$  is a solution for ${\displaystyle g(\Phi (p))}$ . The maps ${\displaystyle \Phi ,\Psi }$  are often called forward and backward functional respectively.

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

$${\displaystyle (\forall G\vdash g)(\Psi G\Phi \vdash f).}$$

 

See also

• Wadge reducibility

References

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. The Degrees of Discontinuity of some Translators between Representations of the Real Numbers (Report). International Computer Science Institute. 1992.