Completion of choice (Q2220486): Difference between revisions

The authors carry out Weihrauch analysis of completions of choice problems in many settings. In general, a choice problem \(C_X\) selects an element from a closed nonempty subset of the space \(X\), where the subset is described by negative information. The completion of a problem \(f\), denoted \(\bar f\), is a total problem that outputs \(f(x)\) if \(x\) is in the domain of \(f\) and the closure of the range space of \(f\) otherwise. The completion of a choice problem may or may not be Weihrauch equivalent to the original problem. For example, \(C_{\mathbb N}\) is not Weihrauch equivalent to \(\overline {C_{\mathbb N}}\), while \(C_{2^{\mathbb N}}\) is Weihrauch equivalent to \(\overline{C_{2^{\mathbb N}}}\). The authors consider choice over many spaces, variations of choice including compact and positive measure versions, totalizations other than completion, and interactions with jump and composition. For a survey of choice problems, see [\textit{V. Brattka} et al., ``Weihrauch complexity in computable analysis'', in Handbook of computability and complexity in analysis. Cham: Springer. 367--417 (2021; \url{doi:10.1007/978-3-030-59234-9_11)}].