Completion of choice

DOI10.1016/J.APAL.2020.102914MaRDI QIDQ2220486zbMATH OpenOpenAlexFDO

Authors Vasco Brattka, Guido Gherardi

Publication date 25 January 2021

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.13186

zbMATH Keywords

choice problemsclasses of computable problemscompletioncomputable analysiscomputable reducibilitytotal Weihrauch reducibilitytotalizationWeihrauch complexityWeihrauch latticeWeihrauch reducibility

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Other degrees and reducibilities in computability and recursion theory (03D30) Computation over the reals, computable analysis (03D78) Second- and higher-order arithmetic and fragments (03F35) Constructive and recursive analysis (03F60)

Abstract: We systematically study the completion of choice problems in the Weihrauch lattice. Choice problems play a pivotal role in Weihrauch complexity. For one, they can be used as landmarks that characterize important equivalences classes in the Weihrauch lattice. On the other hand, choice problems also characterize several natural classes of computable problems, such as finite mind change computable problems, non-deterministically computable problems, Las Vegas computable problems and effectively Borel measurable functions. The closure operator of completion generates the concept of total Weihrauch reducibility, which is a variant of Weihrauch reducibility with total realizers. Logically speaking, the completion of a problem is a version of the problem that is independent of its premise. Hence, studying the completion of choice problems allows us to study simultaneously choice problems in the total Weihrauch lattice, as well as the question which choice problems can be made independent of their premises in the usual Weihrauch lattice. The outcome shows that many important choice problems that are related to compact spaces are complete, whereas choice problems for unbounded spaces or closed sets of positive measure are typically not complete.

Review text

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)}].

Recommendations

• Closed choice and a uniform low basis theorem
• Weihrauch goes Brouwerian
• Effective Choice and Boundedness Principles in Computable Analysis
• Effective choice and boundedness principles in computable analysis
• Closed choice for finite and for convex sets

Cites work

• A Galois connection between Turing jumps and limits
• A topological view on algebraic computation models
• Borel Complexity of Topological Operations on Computable Metric Spaces
• Closed choice and a uniform low basis theorem
• Connected choice and the Brouwer fixed point theorem
• Effective Choice and Boundedness Principles in Computable Analysis
• Finite choice, convex choice and finding roots
• scientific article; zbMATH DE number 3987247 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• scientific article; zbMATH DE number 1390024 (Why is no real title available?)
• Joins in the strong Weihrauch degrees
• Monte Carlo computability
• On the algebraic structure of Weihrauch degrees
• On the uniform computational content of computability theory
• On the uniform computational content of Ramsey's theorem
• On the uniform computational content of the Baire category theorem
• Probabilistic computability and choice
• Subsystems of second order arithmetic
• The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
• The Vitali Covering Theorem in the Weihrauch Lattice
• Theory of representations
• Weihrauch degrees, omniscience principles and weak computability
• Weihrauch degrees, omniscience principles and weak computability

Cited in

(18)

• On the Weihrauch degree of the additive Ramsey theorem over the rationals
• The fixed-point property for represented spaces
• The computational strength of matchings in countable graphs
• Closed choice and a uniform low basis theorem
• Weihrauch-completeness for layerwise computability
• THE OPEN AND CLOPEN RAMSEY THEOREMS IN THE WEIHRAUCH LATTICE
• Stashing and parallelization pentagons
• Continuous and monotone machines
• FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
• Closed choice for finite and for convex sets
• Weihrauch goes Brouwerian
• Algebraic properties of the first-order part of a problem
• THE DISCONTINUITY PROBLEM
• Notes on overt choice
• The Weihrauch lattice at the level of \(\boldsymbol{\Pi }^1_1{-}\mathsf{CA}_0\): the Cantor-Bendixson theorem
• Indivisibility and uniform computational strength
• On the Weihrauch degree of the additive Ramsey theorem
• Sequential discontinuity and first-order problems

This page was built for publication: Completion of choice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220486)