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. It was originally introduced by Klaus Weihrauch in an unpublished 1992 technical report.

Definition

A represented space is a pair $(X,\delta )$ of a set $X$ and a surjective partial function $\delta :\subset {\mathbb{N}}^{\mathbb{N}}\to 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{d}\mathrm{o}\mathrm{m}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⊢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 $\mathrm{\Phi },\mathrm{\Psi }:\subset {\mathbb{N}}^{\mathbb{N}}\to {\mathbb{N}}^{\mathbb{N}}$ such that$$(\mathrm{\forall }G⊢g)(\mathrm{\Psi }⟨\mathrm{i}\mathrm{d},G\mathrm{\Phi }⟩⊢f),$$where $\mathrm{\Psi }⟨\mathrm{i}\mathrm{d},G\mathrm{\Phi }⟩:=⟨p,q⟩\mapsto \mathrm{\Psi }(⟨p,G\mathrm{\Phi }(q)⟩)$ and $⟨\cdot ⟩$ denotes the join in the Baire space. Very often, in the literature we find $\mathrm{\Psi }$ written as a binary function, so to avoid the use of the join.Template:Citation needed In other words, $f{\le }_{\mathrm{W}}g$ if there are two computable maps $\mathrm{\Phi },\mathrm{\Psi }$ such that the function $p\mapsto \mathrm{\Psi }(p,q)$ is a realizer for $f$ whenever $q$ is a solution for $g(\mathrm{\Phi }(p))$. The maps $\mathrm{\Phi },\mathrm{\Psi }$ are often called forward and backward functional respectively.

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

See also

• Wadge reducibility

References

Template:Comp-sci-stub Template:Mathlogic-stub