Forests describing Wadge degrees and topological Weihrauch degrees of certain computational problems

What is it about?

Reducibility relations are natural tools for comparing computational problems with respect to their computational complexity. In this article three topological reducibility relations are considered. They are (1) Wadge reducibility, (2) continuous strong Weihrauch reducibility, and (3) continuous Weihrauch reducibility We associate with computational problems certain labeled forests and trees and show that Wadge reducibility, continuous strong Weihrauch reducibility and continuous Weihrauch reducibility between such problems can be characterized by suitable reducibility relations between the associated forests when they are defined.

Featured Image

Why is it important?

This gives us a combinatorial description of the initial segments of these three reducibility hierarchies for large classes of computational problems.