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] A represented space is a pair
, δ )
and a surjective partial function
δ :⊂
δ
δ
be represented spaces and let
be a partial multi-valued function.
is a (possibly partial) function
δ
Intuitively, a realizer
" but it works on names.
be represented spaces and let
be partial multi-valued functions.
is Weihrauch reducible to
, if there are computable partial functions
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
are often called forward and backward functional respectively.
is strongly Weihrauch reducible to
, if the backward functional
does not have access to the original input.
This computer science article is a stub.
You can help Wikipedia by expanding it.This mathematical logic-related article is a stub.
You can help Wikipedia by expanding it.