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 [math]\displaystyle{ (X,\delta) }[/math] of a set [math]\displaystyle{ X }[/math] and a surjective partial function [math]\displaystyle{ \delta:\subset \mathbb{N}^{\mathbb{N}}\rightarrow X }[/math].[1]
Let [math]\displaystyle{ (X,\delta_X),(Y,\delta_Y) }[/math] be represented spaces and let [math]\displaystyle{ f:\subset X \rightrightarrows Y }[/math] be a partial multi-valued function. A realizer for [math]\displaystyle{ f }[/math] is a (possibly partial) function [math]\displaystyle{ F:\subset \mathbb{N}^\mathbb{N} \to \mathbb{N}^\mathbb{N} }[/math] such that, for every [math]\displaystyle{ p \in \mathrm{dom} f \circ \delta_X }[/math], [math]\displaystyle{ \delta_Y \circ F (p) = f\circ \delta_X(p) }[/math]. Intuitively, a realizer [math]\displaystyle{ F }[/math] for [math]\displaystyle{ f }[/math] behaves "just like [math]\displaystyle{ f }[/math]" but it works on names. If [math]\displaystyle{ F }[/math] is a realizer for [math]\displaystyle{ f }[/math] we write [math]\displaystyle{ F \vdash f }[/math].
Let [math]\displaystyle{ X,Y,Z,W }[/math] be represented spaces and let [math]\displaystyle{ f:\subset X \rightrightarrows Y, g:\subset Z \rightrightarrows W }[/math] be partial multi-valued functions. We say that [math]\displaystyle{ f }[/math] is Weihrauch reducible to [math]\displaystyle{ g }[/math], and write [math]\displaystyle{ f\le_{\mathrm{W}} g }[/math], if there are computable partial functions [math]\displaystyle{ \Phi,\Psi:\subset \mathbb{N}^\mathbb{N} \to \mathbb{N}^\mathbb{N} }[/math] such that[math]\displaystyle{ (\forall G \vdash g )( \Psi \langle \mathrm{id}, G\Phi \rangle \vdash f ), }[/math]where [math]\displaystyle{ \Psi \langle \mathrm{id}, G\Phi \rangle:= \langle p,q\rangle \mapsto \Psi(\langle p, G\Phi(q) \rangle) }[/math] and [math]\displaystyle{ \langle \cdot \rangle }[/math] denotes the join in the Baire space. Very often, in the literature we find [math]\displaystyle{ \Psi }[/math] written as a binary function, so to avoid the use of the join.[citation needed] In other words, [math]\displaystyle{ f \le_\mathrm{W} g }[/math] if there are two computable maps [math]\displaystyle{ \Phi, \Psi }[/math] such that the function [math]\displaystyle{ p \mapsto \Psi(p, q) }[/math] is a realizer for [math]\displaystyle{ f }[/math] whenever [math]\displaystyle{ q }[/math] is a solution for [math]\displaystyle{ g(\Phi(p)) }[/math]. The maps [math]\displaystyle{ \Phi, \Psi }[/math] are often called forward and backward functional respectively.
We say that [math]\displaystyle{ f }[/math] is strongly Weihrauch reducible to [math]\displaystyle{ g }[/math], and write [math]\displaystyle{ f\le_{\mathrm{sW}} g }[/math], if the backward functional [math]\displaystyle{ \Psi }[/math] does not have access to the original input. In symbols:[math]\displaystyle{ (\forall G \vdash g )( \Psi G\Phi \vdash f ). }[/math]
See also
- Wadge reducibility
References
- ↑ 1.0 1.1 Brattka, Vasco; Gherardi, Guido; Pauly, Arno (2021), Brattka, Vasco; Hertling, Peter, eds., "Weihrauch Complexity in Computable Analysis" (in en), Handbook of Computability and Complexity in Analysis (Cham: Springer International Publishing): pp. 367–417, doi:10.1007/978-3-030-59234-9_11, ISBN 978-3-030-59233-2, https://link.springer.com/10.1007/978-3-030-59234-9_11, retrieved 2022-06-29
- ↑ The Degrees of Discontinuity of some Translators between Representations of the Real Numbers (Report). International Computer Science Institute. 1992. https://www.icsi.berkeley.edu/icsi/node/2486.
 |  |
