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^\rightarrow X$.

Let $(X,\delta_X),(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^\mathbb \to \mathbb^\mathbb$ such that, for every $p \in \mathrm 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_ g$, if there are computable partial functions $\Phi,\Psi:\subset \mathbb^\mathbb \to \mathbb^\mathbb$ such that$(\forall G \vdash g )( \Psi \langle \mathrm, G\Phi \rangle \vdash f ),$where $\Psi \langle \mathrm, 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. In other words, $f \le_\mathrm 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_ 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 ).$

See also

* Wadge reducibility

References

Computable analysis

{{Mathlogic-stub