A represented space is a pair of a set and a surjective partial function :\subset \mathbb {N} ^{\mathbb {N} }\rightarrow X}
.[1]
Let be represented spaces and let be a partial multi-valued function. A realizer for is a (possibly partial) function such that, for every , . Intuitively, a realizer for behaves "just like " but it works on names. If is a realizer for we write .
Let be represented spaces and let be partial multi-valued functions. We say that is Weihrauch reducible to , and write , if there are computable partial functions :\subset \mathbb {N} ^{\mathbb {N} }\to \mathbb {N} ^{\mathbb {N} }}
such that
where :=\langle p,q\rangle \mapsto \Psi (\langle p,G\Phi (q)\rangle )}
and denotes the join in the Baire space. Very often, in the literature we find written as a binary function, so to avoid the use of the join.[citation needed] In other words, if there are two computable maps such that the function is a realizer for whenever is a solution for . The maps are often called forward and backward functional respectively.
We say that is strongly Weihrauch reducible to , and write , if the backward functional does not have access to the original input. In symbols: