Weihrauch reducibility

What is Weihrauch reducibility?

Weihrauch reducibility is a framework to compare how non-computable problems are. A problem A being Weihrauch reducible to B means that there is an otherwise computable procedure to solve A that invokes solving B as a subroutine exactly once. Clearly, this means that A is at most as non-computable as B. The Weihrauch degrees are the equivalence classes for Weihrauch reducibility. While Weihrauch reducibility is a kind of many-one reducibility, we nevertheless find that other familiar degree structures embed into the Weihrauch degrees, for example the Turing degrees, enumeration degrees and Medvedev degrees. The Weihrauch degrees carry a rich algebraic structure, i.e. are equipped with operations allowing us to construct new Weihrauch degrees from given ones. For example, the Weihrauch degree A* describes the ability to ask a finite tuple of questions to A all at once. Amongst other things, the Weihrauch degrees are a distributive lattice.

Why study Weihrauch reducibility?

The original motivation to explore Weihrauch reducibility was as a setting for a meta-mathematical investigation. Many theorems can be seen as a computational task. Brouwer's Fixed Point theorem, for example, asserts that every continuous self-map on the unit hypercube has a fixed point. This naturally gives rise to the computational task of finding a fixed point, given a continuous function. Understanding how non-computable this task is (and indeed, we cannot compute the Brouwer fixed points) tells us something about how non-constructive the theorem is. There is a practical use for the study of Weihrauch degrees, too. Many problems of interest for scientific computing are in fact non-computable as commonly stated. Knowing their Weihrauch degree lets us discern what approximations or other relaxations might turn them into computable problems. In this approach, we can make sure that we compute as much as we could possibly compute. From a purely internal perspective, the Weihrauch degrees give rise to a plethora of questions with interesting yet attainable answers - I find it great fun to figure those out.

How to work with Weihrauch reducibility?

There are a number of Weihrauch degrees we understand well - the Weihrauch zoo. When studying a new computational task, the main goal is to understand how this new task is located relative to the established ones. Often it will just turn out to be equivalent to a previously studied task. If not, we can explore to what known tasks the new one is reducible to, and what known tasks are reducible to the new one. Proving reductions is often very algorithmic in nature. This is unsurprising, given the definition of Weihrauch reducibility: We just need to come up with an algorithm to solve one problem using a solution to the other problem as a black box. Separations are generally harder to prove. We do have a handful of useful techniques for this, though.

Read more

A formal introduction to and survey of Weihrauch reducibility is found here. A bibliography listing papers on Weihrauch reducibility is available here.


Photo of Arno Pauly

E-mail page maintainer