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.
