A major goal of contemporary mathematics is that of classifying structures and relations according to their complexity. Common questions in this direction are as follows: how much information is needed to solve a specific problem about a structure? Given two different structures, which one is more complicated? Computable structure theory is a vast research program that provides a formal setting in which this kind of questions can be formulated. In particular, in this field we aim at investigating the interplay between the algebraic content of a structure, expressed by the structural properties that it satisfies, and its algorithmic complexity, which corresponds to how much is difficult to compute or describe the structure.  The present project is part of this thread of research.

Our main focus is on computable reducibility, a long-standing notion that has proven to be a very powerful tool for ranking the complexity of equivalence relations over the set of natural numbers. Computable reducibility is a 2-dimensional version of the classical m-reducibility between set of natural numbers from different point of views such as, e.g., representing a computable analogue of Borel reducibility, as a convenient tool for measuring the complexity of isomorphism relations between computable structures, and as part of the so-called theory of numberings.

The goal of this project is two-fold.
On the one hand, we aim at extending the scope of computable reducibility from equivalence relations to more general cases, such as graphs, partial orders, and arbitrary binary relations. In particular, we are interested in characterzing universal relations, i.e., relations that contain so much information that all others computably reduce to them. More generally, we want to investigate how the degree-structure induced by computable reducibility on a family of relation satisfying a property P change as P changes.
On the other hand, we want to relax the notion of computable reducibility by analyzing cases in which a reduction cannot be perfomed algorithmically and only with the help of some additional information. In doing so, in analogy with many others notions of computable structure theory, we will associate to each pair of equivalence relations two corresponding spectra of Turing degrees: the reducibility and bi-reducibility spectrum. These new spectra allow to nicely calibrate the complexity of all possible of way reducing an equivalence relation to another.

In a nutshell the present project is thus designed to hopefully unleash the full potential of a notion whose fruitfulness as a classification tool is well-know and proved but for a yet limited case.