Completion of Choice

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.

arXiv comment30 pages

References in corpus (12)

• Closed Choice and a Uniform Low Basis Theorem
• The Bolzano-Weierstrass Theorem is the Jump of Weak König's Lemma
• Effective Choice and Boundedness Principles in Computable Analysis
• Weihrauch Degrees, Omniscience Principles and Weak Computability
• Probabilistic Computability and Choice
• Finite choice, convex choice and finding roots
• Connected Choice and the Brouwer Fixed Point Theorem
• On the Uniform Computational Content of Ramsey's Theorem
• On the Uniform Computational Content of Computability Theory
• Weihrauch goes Brouwerian
• A Galois connection between Turing jumps and limits
• On the Uniform Computational Content of the Baire Category Theorem

Cited by in corpus (11)

• Finding descending sequences through ill-founded linear orders
• Weihrauch goes Brouwerian
• Algebraic properties of the first-order part of a problem
• The Discontinuity Problem
• Searching for an analogue of ATR in the Weihrauch lattice
• The open and clopen Ramsey theorems in the Weihrauch lattice
• Stashing And Parallelization Pentagons
• An update on Weihrauch complexity, and some open questions
• The Weihrauch lattice at the level of ${\mathbf{\Pi }}_1^1{-\mathsf{CA}}_0$: the Cantor-Bendixson theorem
• Indivisibility and uniform computational strength
• A jump operator on the Weihrauch degrees