Convex choice, finite choice and sorting

Abstract

We study the Weihrauch degrees of closed choice for finite sets, closed choice for convex sets and sorting infinite sequences over finite alphabets. Our main results are: One, that choice for finite sets of cardinality $i+1$ is reducible to choice for convex sets in dimension $j$, which in turn is reducible to sorting infinite sequences over an alphabet of size $k+1$, iff $i\le j\le k$. Two, that convex choice in dimension two is not reducible to the product of convex choice in dimension one with itself. Three, that sequential composition of one-dimensional convex choice is not reducible to convex choice in any dimension. The latter solves an open question raised at a Dagstuhl seminar on Weihrauch reducibility in 2015. Our proofs invoke Kleene's recursion theorem, and we describe in some detail how Kleene's recursion theorem gives rise to a technique for proving separations of Weihrauch degrees.

References in corpus (1)

• Computation with Advice

Cited by in corpus (1)

• An update on Weihrauch complexity, and some open questions