Finite choice, convex choice and finding roots
arXiv:1302.0380 · doi:10.2168/LMCS-11(4:6)2015
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.
arXiv commentAn earlier version was titled "Closed choice: Cardinality vs convex dimension"
References in corpus (11)
- Closed Choice and a Uniform Low Basis Theorem
- The Bolzano-Weierstrass Theorem is the Jump of Weak König's Lemma
- The degree structure of Weihrauch-reducibility
- Real Hypercomputation and Continuity
- Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees
- Computation with Advice
- Non-deterministic computation and the Jayne-Rogers Theorem
- Connected Choice and the Brouwer Fixed Point Theorem
- Computable Stochastic Processes
- On the topological aspects of the theory of represented spaces
- How constructive is constructing measures?
Cited by in corpus (10)
- On the algebraic structure of Weihrauch degrees
- Connected Choice and the Brouwer Fixed Point Theorem
- Completion of Choice
- Finding descending sequences through ill-founded linear orders
- On the topological aspects of the theory of represented spaces
- Projection operators in the Weihrauch lattice
- How constructive is constructing measures?
- Degrees of incomputability, realizability and constructive reverse mathematics
- The Weihrauch degree of finding Nash equilibria in multiplayer games
- Computability of Initial Value Problems