Weihrauch Complexity: Structuring the Realm of Non-Computability

We give a survey on basic problems, operators and dichotomies in Weihrauch complexity. In particular, we describe how $\mathrm{𝖫𝖯𝖮}$ and $\mathrm{𝖫𝖫𝖯𝖮}$ can be used together with operators such as jump, parallelization, diamond, first-order part, and deterministic part to generate a whole class of very basic and important Weihrauch degrees. We describe how these degrees give natural classes of computable problems and how they match with systems in reverse mathematics. We also briefly discuss the role of closure and interior operators. Finally, we show how some of these degrees also lead to dichotomies for continuous problems with respect to continuous Weihrauch reducibility and different codomains. We close with a brief demonstration of how such dichotomies can be de-uniformized with the help of parallelization in order to obtain dichotomies for computable reducibility.

In recent years, various notions of effectivity and effective reducibility, such as Weihrauch reducibility and realizability, have been adapted to work on sets of arbitrary size by replacing Turing computability with computability by transfinite machine models, such as Koepke’s Ordinal Turing Machines. In this talk, we will give an overview of this area with some of the central results, in particular concerning the mutual effective reducibility between the axioms and axiom schemes of ZFC usually regarded as non-constructive or impredicative, such as the power set axiom, the axiom of choice, and the schemes of separation and replacement.

We prove that continuous reducibility – or topological strong Weihrauch reducibility – on continuous functions from a 0-dimensional analytic domain to a separable metrizable space is a well-quasi-order, or more precisely, a better-quasi-order. To do so, we introduce and describe the class of scattered continuous functions with a 0-dimensional domain.

We construct the category of quasi-Polish spaces as a represented space, which allows us to investigate the computability aspects of some category theoretical constructions, such as functors and limits, within the framework of Type-Two Theory of Effectivity. As an example, we demonstrate the computability of the lower, upper, double, and valuation powerspace endofunctors on the category of quasi-Polish spaces. (This talk was originally presented at the 68th Topology Seminar, August 2021: https://www.mathsoc.jp/section/topology/topsymp.html)

I will discuss recent work studying versions of the tree pigeonhole principle, ${\mathrm{𝖳𝖳}}^1$, in the context of Weihrauch-style computable analysis. The principle has previously been the subject of extensive research in reverse mathematics, an outstanding question of which investigation is whether ${\mathrm{𝖳𝖳}}^1$ is ${\mathrm{\Pi }}_1^1$-conservative over the ordinary pigeonhole principle, ${\mathrm{𝖱𝖳}}^1$. Using the recently introduced notion of the first-order part of an instance-solution problem, we formulate the analogue of this question for Weihrauch reducibility, and give an affirmative answer. In combination with other results, we use this to show that unlike ${\mathrm{𝖱𝖳}}^1$, the problem ${\mathrm{𝖳𝖳}}^1$ is not Weihrauch requivalent to any first-order problem. Our proofs develop new combinatorial machinery for constructing and understanding solutions to instances of ${\mathrm{𝖳𝖳}}^1$. This is joint work with Reed Solomon and Manlio Valenti.

Dilators are particularly uniform transformations of well-orders. Above ${\mathrm{𝖠𝖢𝖠}}_0$, every ${\mathrm{\Pi }}_2^1$ statement corresponds to a dilator, by a classical result of Girard. In contrast, we show that no dilator corresponds to Ramsey’s theorem for pairs and two colours (and the same is true for many other principles from the reverse mathematics zoo). Our proof involves a new principle of slow transfinite ${\mathrm{\Pi }}_2^0$-induction, which admits a recursive counterexample but seems to lie below the Turing jump (though the latter is an open conjecture).

We formalize the notion of Weihrauch reducibility between existence statements in terms of second-order arithmetic [1], which is a standard framework of reverse mathematics. This formalization enables us to determine the strength of verification theories needed for Weihrauch reducibility between existence statements. As an example, we show that for any second-order theory $T$ which is an extension of ${\mathrm{𝖱𝖢𝖠}}_0$, weak König’s lemma with a uniqueness hypothesis is Weihrauch reducible to the identity map in $T$ if and only if $T$ proves weak König’s lemma. This is joint work with Yudai Suzuki.

One approach to studying theorems of general topology in second order arithmetic is to consider the countable second countable spaces, or CSC spaces. There are several classical theorems in general topology which characterize the regular CSC spaces. We go over the strength of some of these theorems in relation to the Big Five systems of second order arithmetic. We also outline how ${\mathrm{𝖠𝖳𝖱}}_0$ proves that regular Hausdorff CSC spaces are a well-quasi-order under embedding.

A countable structure is said to be indivisible if for every presentation and every bounded coloring of the presentation, there is a monochromatic substructure isomorphic to the whole structure. Examples include the natural numbers, Rado and Henson graphs, and nonscattered linear orders. This notion naturally gives rise to an instance-solution problem which outputs such a substructure given a presentation and coloring. We discuss the Weihrauch degrees of these problems in general and for some specific structures, surveying what is known and highlighting current investigations. This is (in part) joint ongoing work with Damir Dzhafarov and Reed Solomon.

We show that a certain initial segment of the degree structure of functions with discrete, possibly infinite, range under continuous Weihrauch reducibility is isomorphic to a hierarchy of labeled forests with respect to a suitable reducibility relation. We also present an explicit calculation of the degree structure of the topological Weihrauch degrees of functions of level of discontinuity at most 4.

There are a number of basis theorems that are equivalent to ${\mathrm{\Sigma }}_2^0$ induction in the reverse mathematics framework. For example, the color basis theorem and the basis theorem for finite dimensional e-matroids are provably equivalent. They are not Weihrauch equivalent. See [1] and [2]. Insights from Weihrauch analysis can motivate interesting reformulations of the reverse mathematics results. Other examples of statements equivalent to ${\mathrm{\Sigma }}_2^0$ induction with various Weihrauch strengths can be found in the recent work of Pauly, Pradic, and Soldà [3].

I will give an overview of generalized Weihrauch reducibility from the perspectives of computability theory, reverse mathematics, and realizability topos theory, with concrete examples and applications. This talk will cover the following topics: compositional product, reduction game, Weihrauch-oracle realizability, constructive reverse mathematics, realizability topos, Lawvere-Tierney topology, subtopos, and extended generalized Weihrauch reducibility.

Splitting methods play a central role in nonsmooth optimization in the design of algorithms for the computation of zeros of maximally monotone set-valued operators in Hilbert spaces which can be written as the sum $A+B$ of two such operators. The main point here is to avoid the use of the resolvent of $A+B$ and to involve only the individual resolvents $J_A,J_B$ of $A$ and $B$ respectively, which may be easier to compute (note that to compute the resolvents of an operator amounts to solving in inverse problem). The most well-studied such algorithms are (i) Tseng’s Splitting Algorithm, (ii) the Forward-Backward Splitting Algorithm, (iii) the Douglas-Rachford Splitting Algorithm and, as the limiting case of (iii), (iv) the Peaceman-Rachford Algorithm (see e.g. [1]).

In [7] and [5], the logic-based proof mining methodology ([2]) is used to extract rates of convergence in certain quantitative forms of uniform monotonicity which give rise to moduli of uniqueness and hence moduli of regularity in the sense of [6]. The existence of such moduli has been studied in terms of reverse mathematics and Weihrauch complexity in [3] and in terms of intuitionistic reverse mathematics recently in [4].

Kruskal’s theorem states that finite trees with labels in a well quasi-order (wqo) form a wqo under infima-preserving embeddings. Nash-Williams proved a version of that theorem for infinite trees, which relies on the stronger notion of better quasi-order [3] (see [1] for the result for labelled trees). That version has not yet been analyzed in an appropriate context, such as that of reverse mathematics. On the other hand, a number of weaker results about the structure of trees with labels in a better quasi-order have been studied, often in relation to open problems such as the strength of Fraïssé’s conjecture [2]. We review the currently available results from the point of view of reverse mathematics and discuss some new ones, as well as some ideas for future research.

We address the classification of different fragments of the Galvin-Prikry theorem in terms of their uniform computational content. We show that functions related to the Galvin-Prikry theorem for Borel sets of rank $n$ are strictly between the $(n+1)$th and $n$th iterate of the hyperjump operator. To this end we establish the following result: a Turing jump ideal containing homogeneous sets for all ${\mathrm{\Delta }}_{n+1}^0(X)$ sets must also contain the $n$th hyperjump of $X$. Similar results also hold for Borel sets of transfinite rank. These findings yield a partial refinement of previous results in the reverse mathematics of the Galvin-Prikry theorem. Moreover, in combination with previous results of Marcone and Valenti, they allow us to obtain a fairly complete picture of the Weihrauch degrees of the functions studied.

Consider a problem $P$ with at least one computable instance. Let $P^{\prime }$ be the problem whose instances are indices $n$ such that the $n$th computable partial function ${\varphi }_n$ is an instance of $P$ and such that $P^{\prime }(n)=P({\varphi }_n)$. We investigate the relationship between discontinuity of $P$ and computability of $P^{\prime }$. We show that if $P$ has a computable discontinuity (which we will define) then $P^{\prime }$ is not computable. This fact generalizes many applications of the recursion theorem, such as showing that $P^{\prime }$ is not computable when $P=\mathrm{𝖶𝖪𝖫}$ or $P={\mathrm{𝖱𝖳}}_1^1$. We also pose some questions about how having the index of a solution rather than the set that the index encodes influences Weihrauch reductions.

The algebraic structure of the Weihrauch degrees has long been a subject of study. It is linked to the “inherent logic of computability”. Identifying the Weihrauch degrees as an instance of a previously studied class of structures, in particular one with a logical flavour, could significantly advance our understanding.

Here we study the equational theory of the Weihrauch lattice with multiplication, meaning the collection of equations between terms built from variables, the lattice operations $\bigsqcup$ and $\sqcap$, the product $\times$, and the finite parallelization ${(\cdot )}^{\ast }$ which are true however we substitute Weihrauch degrees for the variables. We provide a combinatorial description of these in terms of a reducibility between finite graphs, and moreover, show that deciding which equations are true in this sense is complete for the third level of the polynomial hierarchy. Pradic has similarly studied the equational structure of the Weihrauch lattice with composition.

I’ll explain that Weihrauch problems can be regarded as containers over the category of subspaces of Baire spaces and computable maps and that Weihrauch reductions correspond exactly to container morphisms. Up to restricting to those containers that do not allow a problem not to answer a question, we get a clean equivalence. We can make similar observations and elaborations regarding extended/generalized/strong Weihrauch reducibility.

In the second part of the talk, I will discuss the equational theory of the Weihrauch lattice equipped with (iterated) composition. Terms in this theory can be translated to alternating automata, and reductions regarded as a somewhat weird kind of simulation. This leads to decidability and a complete axiomatization that includes a generalization of a result of Linda Westrick.

We introduce the class of principal topological spaces. Principal spaces have some bizarre properties which might be useful in Computability Theory. For example, they admit some automatic continuity properties.

Under the Axiom of Choice, principal spaces are very rare: no infinite Hausdorff space is principal under AC. By contrast, in Shelah’s model of set theory and thus under the Axiom of Determinancy a big class of topological spaces relevant to Computable Analysis turn out to be principal, including all computable metric spaces and, more generally, all functionally Hausdorff qcb-spaces.

I was asked to present a brief overview of aspects of degree theory that have been studied throughout the years. The intention was that researchers interested in the Weihrauch degrees may use this as a source for questions that they may pursue. I focused on the following aspects:

I discussed the complexity of the theory of Turing degrees and its fragments when restricted to statements of limited quantifier complexity. I proposed the following questions about the Weihrauch lattice: How complicated are the fragments of the theory of ${𝒟}_{\mathrm{W}}$? At what quantifier level does decidability break down? Are there upper cones of Weihrauch degrees with a decidable/less complicated theory? Specifically, what about the cone above the degree of $\mathrm{id}$?

I discussed the larger structure of the enumeration degrees and ways in which studying the Turing degrees within this larger context has been illuminating. I introduced the enumeration-Weihrauch degrees and suggested the following questions: Can enumeration Weihrauch reducibility be defined entirely in terms of Weihrauch reducibility à la Selman’s theorem? How do other operators on the Weihrauch degrees live inside the ${\le }_{\mathrm{eW}}$-degrees? Are the Weihrauch degrees definable in the ${\le }_{\mathrm{eW}}$-degrees? What is the relationship between problems represented in the ${\le }_{\mathrm{eW}}$-degrees and their total counterparts coming from the Weihrauch degrees?

I discussed local substructures such as the c.e. Turing degrees and ways in which working with them has expanded our toolbox (the priority method). I asked what local structures of the Weihrauch degrees arise naturally or determine the global structure.

Finally I discussed ways in which effective mathematics influences our view of degree structures and helps solve purely structural problems within and asked whether a similar phenomenon can be observed in the Weihrauch lattice.

We answer the following question by Arno Pauly ([1, Open Question 12]): “Is there a square-root operator on the Weihrauch degrees?” In fact, we show that there are uncountably many pairwise incomparable Weihrauch degrees without any roots. We also prove that the omniscience principles $\mathrm{𝖫𝖯𝖮}$ and $\mathrm{𝖫𝖫𝖯𝖮}$ do not have roots.

In this talk, I will provide an overview of what is currently known about the structural properties of the Weihrauch degrees, including some of the more recent results about the existence and properties of chains, antichains, intervals and minimal covers, strong minimal covers, minimal pairs, and embeddings. I will also highlight some open questions and research directions.

In the study of reverse mathematics, the gap between ${\mathrm{𝖠𝖳𝖱}}_0$ and ${\mathrm{\Pi }}_1^1$-${\mathrm{𝖢𝖠}}_0$ is rather large, with many mathematical theorems falling in between. We focus on those theorems which are described by ${\mathrm{\Pi }}_2^1$-sentences and examine the hierarchy above arithmetical transfinite recursion in the context of Weihrauch degrees and reverse mathematics. This is joint work with Yudai Suzuki.

1. 1.

   Brattka defined an interior operator on the Weihrauch degrees called the upper Turing cone version of a problem. This problem is induced by the closure operator on $𝒫({\mathbb{N}}^{\mathbb{N}})$ given by upward closure under Turing reducibility.

   Question: Which other interior operators can we form by considering closure operators on $𝒫({\mathbb{N}}^{\mathbb{N}})$?

2. 2.

   The first-order part of a problem $f$ is the maximum Weihrauch degree of a problem g with codomain $\mathbb{N}$ which reduces to $f$ (Dzhafarov, Solomon, Yokoyama). The $k$-finitary part of a problem $f$ is the maximum Weihrauch degree of a problem g with codomain $𝐤$ which reduces to $f$ (Cipriani, Pauly). Pauly observed during this Dagstuhl meeting that for each represented space $𝐗$ and each problem $f$, the maximum Weihrauch degree among all problems with codomain $𝐗$ which reduce to $f$ exists.

   Question: For which other represented spaces is this maximum useful? How about Sierpinski space?

Recently, Brattka introduced the notion of infinite loop operation on Weihrauch problems. Applying Yoshimura’s unpublished theorem, one can see that the Weihrauch problem $F$ is closed under the infinite loop operation (the inverse limit) if and only if $F$-relative realizability validates the axiom of dependent choice. Therefore, it is an important problem to investigate which Weihrauch problems are closed under the infinite loop operation. Here, we ask about the strength of the infinite loop closure of ${\mathrm{𝖫𝖫𝖯𝖮}}_k$ (all-or-counique choice on $k$).

Question: Is ?

This problem was solved by myself during the conference. That is, ${\mathrm{𝖫𝖫𝖯𝖮}}_k^{\mathrm{\infty }\mathrm{\infty }\mathrm{\infty }\mathrm{\dots }}$ is equivalent to ${\mathrm{𝖣𝖭𝖱}}_k$, and thus the problem is positively resolved.

In the Weihrauch degrees we have an explicit definition of a multi-valued function $f\star g$ such that

In the paper with Gian Marco Osso we define a multi-valued function $f\tilde{\star }g$ such that if $g$ is a cylinder then

$\tilde{\star }$ has some nice properties:

• $\mathrm{■}$

  $(f\tilde{\star }g)\tilde{\star }h{\equiv }_{\mathrm{W}}f\tilde{\star }(g\tilde{\star }h)$;

• $\mathrm{■}$

  $({\mathrm{id}}_{{\mathbb{N}}^{\mathbb{N}}}\times f)\tilde{\star }g{\equiv }_{\mathrm{W}}f\star g$;

• $\mathrm{■}$

  if $g_0{\le }_{\mathrm{W}}{g}_1$, then $f\tilde{\star }{g}_0{\le }_{\mathrm{W}}f\tilde{\star }{g}_1$;

• $\mathrm{■}$

  if $f_0{\le }_{\mathrm{sW}}{f}_1$ and $g_0{\le }_{\mathrm{sW}}{g}_1$, then $f_0\tilde{\star }{g}_0{\le }_{\mathrm{sW}}{f}_1\tilde{\star }{g}_1$.

However, we have examples where $g$ is not a cylinder and ${\max }_{{\le }_{\mathrm{sW}}}\{h\circ k:h{\le }_{\mathrm{sW}}f\wedge k{\le }_{\mathrm{sW}}g\}$ either exists but is not represented by $f\tilde{\star }g$ or does not exist.

It would be interesting to characterize when ${\max }_{{\le }_{\mathrm{sW}}}\{h\circ k:h{\le }_{\mathrm{sW}}f\wedge k{\le }_{\mathrm{sW}}g\}$ exists and in those cases provide an explicit realizer of this strong Weihrauch degree.

Myhill showed that a set $X$ is productive if and only if the complement of the halting set $K$ is 1-reducible to $X$. It follows that the index sets ${\text{Ind}}_n$ for partial computable functions are productive. Let IndRed be the problem which takes $n$ and produces the graph of a 1-reduction from $\overline{K}$ to ${\text{Ind}}_n$. Let IndProd be the problem which takes $n$ and produces a graph of a productive set for ${\text{Ind}}_n$. Myhill’s proofs are uniform in the index: $\text{G}\circ \text{IndRed}$ is Weihrauch equivalent to $\text{G}\circ \text{IndProd}$, where G is the Gödel function which takes a computable set to one of its indices. It turns out that one does not need the index to produce a graph in one of the directions: IndRed is Weihrauch reducible to IndProd.

Questions: Is IndRed Weihrauch equivalent to IndProd? How about to $\text{G}\circ \text{IndRed}$?

A residual lattice is a lattice equipped with a monoidal operator $\ast$ such that for every $f$ and $g$ there are maximum $h$ and $k$ such that $h\ast f\le g$ and $f\ast k\le g$. Given the large number of operators in the Weihrauch lattice, it is natural to ask what are the operators that make the Weihrauch lattice or its dual a residual lattice. Some of these questions have been already answered, but we still miss a complete picture. In particular, it is open whether there always exists a maximum $h$ such that the compositional product $f\ast h$ is Weihrauch reducible to $g$.

Results of the form “If $X$ is well-quasiordered, then so is $F(X)$” for various constructions of quasi-orders $F$ have been a fruitful subject of study in reverse mathematics. Kruskal’s and Higman’s theorems are probably the most famous example, but already “If $\alpha$ is an ordinal, so is $2^{\alpha }$” has non-trivial strength. At first glance, such results don’t seem to have computational content per se. However, we can look at their contrapositives. The algorithmic task then becomes “Given a quasi-order $X$ and a bad sequence in $F(X)$, find a bad sequence in $X$”. The task of finding a bad sequence in a quasi-ordered merely promised to be non-well was studied by Goh, Valenti and the author [1, 2]. By investigating how much the Weihrauch degree decreases if a bad sequence in $F(X)$ is provided as part of the input, we gain insight on how tightly the non-wqo-ness of $F(X)$ and $X$ are linked in an effective way.

Consider the following condition for a real $X\in 2^{\omega }$: $(†)$ if $L$ is a computable linear order on $\omega$ with no computable infinite decreasing sequence, then $X$ doesn’t compute any infinite decreasing sequence for $L$.

Freund and Uftring [1] showed that if $X$ is hyperimmune-free then $X$ satisfies $(†)$. Then, is the condition $(†)$ equivalent to being hyperimmune-free?

Joseph Miller answered this question. If $X$ is $1$-generic, then $X$ satisfies $(†)$, and thus $(†)$ is a strictly weaker notion than being hyperimmune-free.