Weihrauch reducibility explained

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

Definition

A represented space is a pair $(X,\backslash delta)$ of a set

X and a surjective partial function \delta:\subset N ^{N} → 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 N ^{N} \to N ^{N} such that, for every p \in 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 _{W} g , if there are computable partial functions \Phi,\Psi:\subset N ^{N} \to N ^{N} such that$$(\backslash forall\; G\; \backslash vdash\; g)(\backslash Psi\; \backslash langle\; \backslash mathrm,\; G\backslash Phi\; \backslash rangle\; \backslash vdash\; f),$$where \Psi \langle id , G\Phi \rangle: = \langle p,q\rangle \mapsto \Psi(\langle p, G\Phi(q) \rangle) and \langle ⋅ \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 _{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 _{sW} g , if the backward functional \Psi does not have access to the original input. In symbols:$$(\backslash forall\; G\; \backslash vdash\; g)(\backslash Psi\; G\backslash Phi\; \backslash vdash\; f).$$

Notes and References

1. Weihrauch . Klaus . The Degrees of Discontinuity of some Translators between Representations of the Real Numbers . Informatik-Berichte . 129 . FernUniversität in Hagen . 1992 .