Finite choice, convex choice and finding roots

DOI10.2168/LMCS-11(4:6)2015MaRDI QIDQ3460409zbMATH OpenOpenAlexFDO

Authors Stéphane Le Roux, Arno Pauly

Publication date 7 January 2016

Published in Logical Methods in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

closed choicereverse mathematicsWeihrauch reducibility

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Computation over the reals, computable analysis (03D78) Constructive and recursive analysis (03F60)

Abstract: We investigate choice principles in the Weihrauch lattice for finite sets on the one hand, and convex sets on the other hand. Increasing cardinality and increasing dimension both correspond to increasing Weihrauch degrees. Moreover, we demonstrate that the dimension of convex sets can be characterized by the cardinality of finite sets encodable into them. Precisely, choice from an n+1 point set is reducible to choice from a convex set of dimension n, but not reducible to choice from a convex set of dimension n-1. Furthermore we consider searching for zeros of continuous functions. We provide an algorithm producing 3n real numbers containing all zeros of a continuous function with up to n local minima. This demonstrates that having finitely many zeros is a strictly weaker condition than having finitely many local extrema. We can prove 3n to be optimal.

Recommendations

• Closed choice for finite and for convex sets
• Connected choice and the Brouwer fixed point theorem
• On the computational content of the Brouwer fixed point theorem
• Effective Choice and Boundedness Principles in Computable Analysis
• Effective choice and boundedness principles in computable analysis

Cited in

(16)

• Comparing representations for function spaces in computable analysis
• Completion of choice
• Finite choice, convex choice and sorting
• How constructive is constructing measures?
• The Brouwer fixed point theorem revisited
• On the algebraic structure of Weihrauch degrees
• Computability of Subsets of Metric Spaces
• Weihrauch Complexity in Computable Analysis
• FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
• Connected choice and the Brouwer fixed point theorem
• Closed choice for finite and for convex sets
• Representations of analytic functions and Weihrauch degrees
• Notes on overt choice
• Computability of initial value problems
• On the Weihrauch degree of the additive Ramsey theorem
• The Dyck and the Preiss separation uniformly

This page was built for publication: Finite choice, convex choice and finding roots

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