Completion of choice

DOI10.1016/J.APAL.2020.102914zbMATH Open1462.03019arXiv1910.13186OpenAlexW2982356607MaRDI QIDQ2220486FDOQ2220486

Authors: Vasco Brattka, Guido Gherardi 

Publication date: 25 January 2021

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

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.

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

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

zbMATH Keywords

computable analysiscompletionWeihrauch reducibilitytotalizationchoice problemsWeihrauch latticecomputable reducibilityclasses of computable problemstotal Weihrauch reducibilityWeihrauch complexity

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

• Continuous and monotone machines
• On the Weihrauch degree of the additive Ramsey theorem over the rationals
• Closed choice for finite and for convex sets
• The computational strength of matchings in countable graphs
• Closed choice and a uniform low basis theorem
• Notes on overt choice
• Weihrauch goes Brouwerian
• The fixed-point property for represented spaces
• Algebraic properties of the first-order part of a problem
• FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
• THE OPEN AND CLOPEN RAMSEY THEOREMS IN THE WEIHRAUCH LATTICE
• Weihrauch-completeness for layerwise computability
• Title not available (Why is that?)
• THE DISCONTINUITY PROBLEM

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)