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.{{Citation |last1=Brattka |first1=Vasco |title=Weihrauch Complexity in Computable Analysis |date=2021 |url=https://link.springer.com/10.1007/978-3-030-59234-9_11 |work=Handbook of Computability and Complexity in Analysis |pages=367–417 |editor-last=Brattka |editor-first=Vasco |place=Cham |publisher=Springer International Publishing |language=en |doi=10.1007/978-3-030-59234-9_11 |isbn=978-3-030-59233-2 |access-date=2022-06-29 |last2=Gherardi |first2=Guido |last3=Pauly |first3=Arno |s2cid=7903709 |editor2-last=Hertling |editor2-first=Peter|arxiv=1707.03202 }} It was originally introduced by Klaus Weihrauch in an unpublished 1992 technical report.{{cite report | last=Weihrauch | first=Klaus | title=The Degrees of Discontinuity of some Translators between Representations of the Real Numbers | series=Informatik-Berichte | volume=129 | publisher=FernUniversität in Hagen | date=1992 | url=https://nbn-resolving.org/urn:nbn:de:hbz:708-dh6698}}

Definition

A represented space is a pair $(X,\delta)$ of a set $X$ and a surjective partial function $\delta:\subset \mathbb{N}^{\mathbb{N}}\rightarrow X$ .

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\le_{\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|date=June 2022}} In other words, $f \le_\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\le_{\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

Category:Computable analysis

Weihrauch reducibility

Definition

See also

References